Spatial query processing in an object-oriented database system
Jack A. Orenstein · Proceedings - ACM-SIGMOD International Conference on Management of Data · 1986
DBMSs must offer spatial query processing capabilities to meet the needs of applications such as cartography, geographic information processing and CAD. Many data structures and algorithms that process grid representations of spatial data have appeared in the literature. We unify much of this work by identifying common principles and distilling them into a small set of constructs. (Published data structures and algorithms can be derived as special cases.) We show how these constructs can be supported with only minor modifications to current DBMS implementations. The ideas are demonstrated in the context of the range query problem. Analytical and experimental evidence indicates that performance of the derived solution is very good (e.g., comparable to performance of the kd tree.)
Cited by 184 works. doi:10.1145/16894.16886 Open-access PDF
Authors
References
- Data Structures for Range Searching
- An effective way to represent quadtrees
- A class of data structures for associative searching
- On extending the functions of a relational database system
- Interpolation-based index maintenance
- A class of data structures for associative searching
- Relational Information Systems
- Interpolation-based index maintenance