Spatial query processing in an object-oriented database system

15 June 1986

journal article
Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record

Vol. 15 (2) , 326-336
https://doi.org/10.1145/16856.16886

Abstract

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.)

Keywords

This publication has 15 references indexed in Scilit:

The Grid File
ACM Transactions on Database Systems, 1984
A class of data structures for associative searching
Published by Association for Computing Machinery (ACM) ,1984
A data structure and algorithm based on a linear key for a rectangle retrieval problem
Computer Vision, Graphics, and Image Processing, 1983
Localized set operations for solid modeling
Published by Association for Computing Machinery (ACM) ,1983
Interpolation-based index maintenance
Published by Association for Computing Machinery (ACM) ,1983
An effective way to represent quadtrees
Communications of the ACM, 1982
On extending the functions of a relational database system
Published by Association for Computing Machinery (ACM) ,1982
Picture Query Languages for Pictorial Data-Base Systems
Computer, 1981
Data Structures for Range Searching
ACM Computing Surveys, 1979
Multidimensional binary search trees used for associative searching
Communications of the ACM, 1975