Back to Search
Start Over
EFFICIENT NON-INTERSECTION QUERIES ON AGGREGATED GEOMETRIC DATA.
- Source :
- International Journal of Computational Geometry & Applications; Dec2009, Vol. 19 Issue 6, p479-506, 28p, 2 Diagrams, 2 Charts
- Publication Year :
- 2009
-
Abstract
- Geometric intersection searching problems are a well-studied class of query-retrieval problems with many applications. The goal here is to preprocess a set of geometric objects so that the ones that are intersected by a query object can be reported efficiently. Often, a more general version of the problem arises, where the data comes aggregated in disjoint groups and of interest are the groups, not the individual objects, that are intersected by the query object. One approach to a generalized problem is to ignore the grouping, solve the corresponding classical problem, and then infer the groups from the reported answer. However, this is not efficient, since the number of objects intersected can be much larger than the number of groups (i.e., the output size). The problem of designing efficient, output-sensitive query algorithms for generalized intersection searching has received much attention in recent years, and such solutions have been developed for several problems. This paper considers a new class of generalized query-retrieval problems. Specifically, given aggregated geometric data the goal is to report the distinct groups such that no objects from those groups are intersected by the query. Of interest in these generalized non-intersection searching problems are solutions where the query time is sensitive to the output size, i.e., the number of groups reported. Unfortunately, the obvious approaches of (i) solving the corresponding generalized intersection searching problem and reporting the complement, or (ii) solving a generalized intersection searching problem with the complement of the query are either inefficient or incorrect. This paper provides efficient, output-sensitive solutions to several generalized non-intersection searching problems, using techniques such as geometric duality, sparsification, persistence, filtering search, and pruning. [ABSTRACT FROM AUTHOR]
- Subjects :
- GEOMETRIC analysis
ALGORITHMS
DATA
GEOMETRY
INFORMATION storage & retrieval systems
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 19
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 47377915
- Full Text :
- https://doi.org/10.1142/S0218195909003088