Spatial Indexing: Past and Future.

Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
  author    = {Hongjun Lu and
               Beng Chin Ooi},
  title     = {Spatial Indexing: Past and Future},
  journal   = {IEEE Data Eng. Bull.},
  volume    = {16},
  number    = {3},
  year      = {1993},
  pages     = {16-21},
  ee        = {db/journals/debu/LuO93.html},
  bibsource = {DBLP,}


Efficient processing of queries in spatial database systems relies upon auxiliary indexing structures. A large number of spatial indexing structures have been proposed. In this short paper, we examine the basic issues in indexing spatial data, classify the existing indexing mechanisms according to their underlying data structures and the techniques used to handle non-zero sized objects, and briefly discuss future research directions.

Copyright © 1993 by the author(s). Abstract used with permission.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 1 Issue 2, SIGMOD '75-'92" and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition:

Data Engineering Bulletin September 1993: Geographic Information Systems (Kyu-Young Whang, ed.)
( letter+figures , letter-figures , A4+figures , A4-figures , PDF+figures)


Jay Banerjee, Won Kim: Supporting VLSI Geometry Operations in a Database System. ICDE 1986: 409-415 BibTeX
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388 BibTeX
Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331 BibTeX
Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159 BibTeX
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 BibTeX
Oliver Günther, Alejandro P. Buchmann: Research Issues in Spatial Databases. SIGMOD Record 19(4): 61-68(1990) BibTeX
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363 BibTeX
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 BibTeX
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379 BibTeX
David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304 BibTeX
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multikey File Structure. ACM Trans. Database Syst. 9(1): 38-71(1984) BibTeX
Yutaka Ohsawa, Masao Sakauchi: A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database. ICDE 1990: 296-303 BibTeX
Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Spatial indexing in binary decomposition and spatial bounding. Inf. Syst. 16(2): 211-237(1991) BibTeX
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben: The Transformation Technique for Spatial Objects Revisited. SSD 1993: 73-88 BibTeX
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 BibTeX
Markku Tamminen: Efficient Spatial Access to a Data Base. SIGMOD Conference 1982: 200-206 BibTeX
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 BibTeX

Referenced by

  1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  2. Hongjun Lu, Beng Chin Ooi, Kian-Lee Tan: On Spatially Partitioned Temporal Join. VLDB 1994: 546-557
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
Bulletin of the IEEE Computer Society Technical Committee on Data Engineering: Copyright © by IEEE,
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:56:10 2009