ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Spatial Indexing: Past and Future.

Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)
@article{DBLP:journals/debu/LuO93,
  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, http://dblp.uni-trier.de}
}

Abstract

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

Online Edition:

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

References

[AbS83]
...
[BaK86]
Jay Banerjee, Won Kim: Supporting VLSI Geometry Operations in a Database System. ICDE 1986: 409-415 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ben75]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BIM90]
Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[BKS90]
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 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[FaR91]
Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Fre87]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gre89]
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gun88]
...
[GuB90]
Oliver Günther, Alejandro P. Buchmann: Research Issues in Spatial Databases. SIGMOD Record 19(4): 61-68(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Gut84]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW88]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The Twin Grid File: A Nearly Space Optimal Index Structure. EDBT 1988: 352-363 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW89]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HoS92]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[HSW90]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[LoS89]
David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[MHN84]
...
[NHS84]
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) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ohle92]
...
[OhS83]
...
[OhS90]
Yutaka Ohsawa, Masao Sakauchi: A New Tree Type Data Structure with Homogeneous Nodes Suitable for a Very Large Spatial Database. ICDE 1990: 296-303 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[OMS87]
...
[OSM91]
Beng Chin Ooi, Ron Sacks-Davis, Ken J. McDonell: Spatial indexing in binary decomposition and spatial bounding. Inf. Syst. 16(2): 211-237(1991) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ore86]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[PST93]
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben: The Transformation Technique for Spatial Objects Revisited. SSD 1993: 73-88 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Rob81]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[RoL85]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Ros85]
...
[SeK88]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SeK90]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SRF87]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[SiW88]
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[Tam82]
Markku Tamminen: Efficient Spatial Access to a Data Base. SIGMOD Conference 1982: 200-206 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[WhK85]
Kyu-Young Whang, Ravi Krishnamurthy: The Multilevel Grid File - A Dynamic Hierarchical Multidimensional File Structure. DASFAA 1991: 449-459 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML

Copyright © Fri Mar 12 17:26:37 2010 by Michael Ley (ley@uni-trier.de)