Spatial search with polyhedra
Published 4 December 2002
H. V. Jagadish
Citations97
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown how to use multiattribute search structures for polyhedral regions by mappingpolyhedral regions into rectangular regions of a higher dimension and the P-tree (polyhedral tree) is introduced and shown to be an effective multiattribute index structure.
Abstract
Range searches in multidimensional space have been studied extensively, and several excellent search structures have been devised. However, all of these require that the ranges in the different dimensions be specified independently. In other words, only rectangular regions can be specified and searched for. Similarly, nonpoint objects can be indexed only in terms of their bounding rectangles. However, polyhedral search regions and polyhedral bounding rectangles can often provide a much greater selectivity in the search. It is shown how to use multiattribute search structures for polyhedral regions by mapping polyhedral regions into rectangular regions of a higher dimension. In particular, the P-tree (polyhedral tree) is introduced and shown to be an effective multiattribute index structure.>
Keywords
Computer Science
Communications of the ACMMultidimensional binary search trees used for associative searching
7,467 Citations1975Jon Bentley
The multidimensional binary search tree (or k-d tree) as a data structure for storage of information to be retrieved by associative searches is developed and it is shown to be quite efficient in its storage requirements.
R-trees
6,543 Citations1984Antonin Guttman
A dynamic index structure called an R-tree is described which meets this need, and algorithms for searching and updating it are given and it is concluded that it is useful for current database systems in spatial applications.
ACM Computing SurveysThe Quadtree and Related Hierarchical Data Structures
2,171 Citations1984Hanan Samet
L'accentuation est mise sur la representation de donnees dans les applications de traitement d'images, d'infographie, les systemes d'informations geographiques and the robotique.
Very Large Data BasesThe R+-Tree: A Dynamic Index for Multi-Dimensional Objects
1,263 Citations2018Timos Sellis, Nick Roussopoulos +1 more
A variation to Guttman’s Rtrees (R+-trees) that avoids overlapping rectangles in intermediate nodes of the tree is introduced and analytical results indicate that R+-Trees achieve up to 50% savings in disk accesses compared to an R-tree when searching files of thousands of rectangles.
The K-D-B-tree
885 Citations1981John T. Robinson
A new data structure, the K-D-B-tree, is presented as a solution to the problem of retrieving multikey records via range queries from a large, dynamic index, and it is expected that the multidimensional search effieciency of balanced K-Ds and the I/O efficiency of B-trees should both be approximated in this structure.
ACM Computing SurveysData Structures for Range Searching
622 Citations1979Jon Bentley, Jerome H. Friedman
The purpose of this paper is to acquaint the reader with the structures currently avadable for solving the particular problem of range searching, and to display a set of general methods for attacking multikey searching problems.
A class of data structures for associative searching
395 Citations1984Jack Orenstein, T. H. Merrett
The class of data structures generated by this scheme includes a type of kd tree whose balance can be efficiently maintained, a multidimensional Btree which is simpler than previously proposed generalizations, and some previously reported data structures for range searching.
Pattern RecognitionAn approach to fingerprint filter design
253 Citations1989Lawrence O’Gorman, Jeffrey V. Nickerson
The contribution of this work is to quantify and justify the functional relationships between image features and filter parameters so that the design process can be easily modified for different conditions of noise and scale.
ACM SIGGRAPH Computer GraphicsSet operations on polyhedra using binary space partitioning trees
229 Citations1987William Thibault, Bruce Naylor
The K-D-B-tree
212 Citations1981John T. Robinson
IEEE Transactions on Software EngineeringGray codes for partial match and range queries
151 Citations1988Christos Faloutsos
The author illustrates the improved clustering of similar records that Gray codes can achieve with multiattribute hashing, and discusses how Gray codes could be applied to some retrieval methods designed for range queries, such as the grid file and the approach based on the so-called z-ordering.
Computer Vision Graphics and Image ProcessingA data structure and algorithm based on a linear key for a rectangle retrieval problem
138 Citations1983David J. Abel, Jocelyn Smith
A structure based on allocation of linear keys developed by a quadtree decomposition of the region is described, together with an algorithm that shows that for a large data base and small search rectangles the number of rectangles in the data base inspected is O(√n).
IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsGeographical Data Structures Compared: A Study of Data Structures Supporting Region Queries
103 Citations1985Jonathan B. Rosenberg
The conclusion of this paper is that in applications where region search (or point search) on large problems is crucial (as in computer-aided design), k-d trees provide superior performance.
Redundancy in spatial databases
94 Citations1989Jack Orenstein
The optimal use of redundancy for z- order is explored through analysis of the z-order search algorithm and through experiments.
A robust multi-attribute search structure
57 Citations2003David Lomet, Betty Salzberg
A multiattribute index structure called the hB-tree is introduced that guarantees decent storage utilization, reasonable-size index terms, and good search and insert performance regardless of key distribution.
Very Large Data BasesA Dual Space Representation for Geometric Data
10 Citations1987Oliver Günther, Eugene Wong
This paper presents a representation echeme for polyhedral objects in arbitrary dimensions and shows how this approach allows UB to decompose set operations on polyhedral objecta into two atepe.