Spatial query processing in an object-oriented database system

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

REFERENCES

• ABEL83: D. J. Abel, J. L. Smlth. k data structure and algorlthm based on a hnear key for a rectangle retrieval problem. Computer Y#s#on, Graphics and Image Processing 27, 1 (1983), 19-31.
• BENT75: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• BENT79: Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
• BURK83: Walter A. Burkhard, Interpolation-based index maintenance, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588070]
• CHAF81: N. 8. Chang, K. S. Fu. Picture query languages for p#ctorml database systems. COMPUTER 14# 11 (1981), 23-33.
• CHAN77: $. K. Chang et al. A relatlonal database system for pictures. Proe. IEEE Workshop on Picture Data Description and Management (1977).
• CHOC84: M. Chock et al. Database structure and mampulatlon capabilities of a p#cture database management system (PICDMS). IEEE Trans on Pattern Analy# and Machine Intelhgence 6, 4 (1984), 484-492.
• DAYA85: U. Dayal et sl. PROBE - a research project m knowledge-oriented database systems: prehmmary analys}s. Technical Report CCA-85-03 (1985), Computer Corporation of America.
• GARG82: Irene Gargantini, An effective way to represent quadtrees, Communications of the ACM, v.25 n.12, p.905-910, Dec 1982 [doi>10.1145/358728.358741]
• HASK82: Roger L. Haskin , Raymond A. Lorie, On extending the functions of a relational database system, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582390]
• LIEN77: Y. E. Lien, D. F. Utter Jr. Design of an Image database. Proe. IEEE Workshop on Picture Data Description and Management (1977).
• LIOU77: J. H. Llou, S. B. Yao. Multldimenmonal elustertug for database orgamzation. {nformatmn Systems 2, 4 (19'/7), 187-198.
• LORI83: R. A. Lorle, W. Plouffe. Relatmnal databases for engineering data. IBM Research Report Rj 384'/(43914) 416/83 (1983).
• MANT83: Martti Mäntylä , Markku Tamminen, Localized set operations for solid modeling, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.279-288, July 25-29, 1983, Detroit, Michigan, United States
• MERR78: T. H. Merrett. Mult#dlmenslonal paging for efficient database querying. Proe. Int'l Conference of Management of Data, Milan (1978), 2'/7-290.
• MERR82: T. H. Merrett, E.J. Otoo. Dynamle multipaging: a storage structure for large shared databases. Proe. 2rid Int'l Conference on Databsses# Improwng Usability and Responsiveness, Jerusalem (1982).
• MERR84: T H Merrett, Relational Information Systems, Reston Publishing Co., Reston, VA, 1984
• NIEV84: J. Nievergelt , Hans Hinterberger , Kenneth C. Sevcik, The Grid File: An Adaptable, Symmetric Multikey File Structure, ACM Transactions on Database Systems (TODS), v.9 n.1, p.38-71, March 1984 [doi>10.1145/348.318586]
• OREN82: J. A. Orenstem. Multidimensional tries used for assocmhve searching. Information Processmg Letters 14, 4 (1982), 150-15'/.
• OREN83: Jack A. Orenstein, Algorithms and data structures for the implementation of a relational database system, 1983
• OREN84: J. A. Orenstein , T. H. Merrett, A class of data structures for associative searching, Proceedings of the 3rd ACM SIGACT-SIGMOD symposium on Principles of database systems, April 02-04, 1984, Waterloo, Ontario, Canada [doi>10.1145/588011.588037]
• OREN85: J. A. Orenstem. Spatial query processing in PROBE. Working paper. To appear as a Teehmcal Report, Computer Corporation of America.
• OUKS83: Mohamed Ouksel , Peter Scheuermann, Storage mappings for multidimensional linear dynamic hashing, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588071]
• ROBI81: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• SCHE82: P. Scheuermann, M. Ouksel. Multidimensional B-trees for associative searching m database systems lnformatzon Systems 7, 2 (1982), 123- 137.
• SMIT84: J. D. Smith. The apphcatmn of data base management systems to spatial data handhng. Project report, Department of Landscape Architecture and Regional Planning, Umvermty of Massachusetts, Amherst (1984).
• STON83: M. Stonebraker et al. Apphcation of abstract data types and abstract indices to CAD data. Proe. ACM SIGMOD conference on engineering design applications (1983).
• STON85: M. Stonebraker. Ineluszon of new types in relational data base systems. Memorandum No. UCB/ERL M85/67, Eleetromcs Research Laboratory, College of Engineering, University of Califorma, Berkeley (1985).
• SAME85a: Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984 [doi>10.1145/356924.356930]
• SAME85b: Hanan Samet , Markku Tamminen, Bintrees, CSG trees, and time, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.121-130, Jul. 1985
• SAME85c: M. Samet, M. TammInen. Computing geometrm propert}es of images represented by linear quadtrees. IEEE Trans. on Pattern Analys#a and Machine Intelhgence 7, 2 (1985), 229-239.
• TAMM81: M. Tammmen. The EXCELL method for effmlent geometrle access to data. Acta Polytechmca Scandmawca, Mathematics and Computer Selenee Series No. 34 (1981).
• TAMM82: Markku Tamminen , Reijo Sulonen, The excell method for efficient geometric access to data, Proceedings of the 19th conference on Design automation, p.345-351, January 1982

INDEX TERMS

Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Cartography
  I.3 COMPUTER GRAPHICS

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Experimentation, Management, Performance