Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation.

@article{DBLP:journals/tkde/GuntherB91,
  author    = {Oliver G{\"u}nther and
               Jeff Bilmes},
  title     = {Tree-Based Access Methods for Spatial Databases: Implementation
               and Performance Evaluation},
  journal   = {IEEE Trans. Knowl. Data Eng.},
  volume    = {3},
  number    = {3},
  year      = {1991},
  pages     = {342-356},
  ee        = {db/journals/tkde/GuntherB91.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1991 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An3-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD2 or /dvd

References

[1]

Dolors Ayala, Pere Brunet, R. Juan, Isabel Navazo: Object Representation by Means of Nonminimal Division Quadtrees and Octrees. ACM Trans. Graph. 4(1): 41-59(1985) BibTeX

[2]

Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX

[3]

...

[4]

Alejandro P. Buchmann, Oliver Günther, Terence R. Smith, Y.-F. Wang (Eds.): Design and Implementation of Large Spatial Databases, First Symposium SSD'89, Santa Barbara, California, July 17/18, 1989, Proceedings. Lecture Notes in Computer Science 409 Springer 1990, ISBN 3-540-52208-5
Contents BibTeX

[5]

Bernard Chazelle: A Theorem on Polygon Cutting with Applications. FOCS 1982: 339-349 BibTeX

[6]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[7]

Max J. Egenhofer, Andrew U. Frank, Jeffrey P. Jackson: A Topological Data Model for Spatial Databases. SSD 1989: 271-286 BibTeX

[8]

Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 BibTeX

[9]

...

[10]

...

[11]

Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 BibTeX

[12]

Oliver Günther, Eugene Wong: A Dual Space Representation for Geometric Data. VLDB 1987: 501-506 BibTeX

[13]

Oliver Günther, Eugene Wong: A Dual Approach to Detect Polyhedral Intersections in Arbitrary Demensions. BIT 31(1): 3-14(1991) BibTeX

[14]

Oliver Günther: Efficient Structures for Geometric Data Management. Lecture Notes in Computer Science Vol. 337 Springer 1988, ISBN 3-540-50463-X
BibTeX

[15]

...

[16]

Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605 BibTeX

[17]

Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX

[18]

...

[19]

Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 BibTeX

[20]

Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 BibTeX

[21]

D. T. Lee, Franco P. Preparata: Computational Geometry - A Survey. IEEE Trans. Computers 33(12): 1072-1101(1984) BibTeX

[22]

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

[23]

Jürg Nievergelt, Klaus Hinrichs: Storage and Access Structures for Geometric Data Bases. FODO 1985: 441-455 BibTeX

[24]

Jürg Nievergelt: 7 ± 2 Criteria for Assessing and Comparing Spatial data Structures. SSD 1989: 3-27 BibTeX

[25]

Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX

[26]

Jack A. Orenstein, Frank Manola: PROBE Spatial Data Modeling and Query Processing in an Image Database Application. IEEE Trans. Software Eng. 14(5): 611-629(1988) BibTeX

[27]

Franco P. Preparata, David E. Muller: Finding the Intersection of n Half-Spaces in Time O(n log n). Theor. Comput. Sci. 8: 45-55(1979) BibTeX

[28]

Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
BibTeX

[29]

John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX

[30]

Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX

[31]

Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984) BibTeX

[32]

Hanan Samet, Robert E. Webber: Storing a Collection of Polygons Using Quadtrees. ACM Trans. Graph. 4(3): 182-222(1985) BibTeX

[33]

Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX

[34]

Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX

[35]

Hans-Werner Six, Peter Widmayer: Hintergrundspeicherstrukturen für ausgedehnte Objekte. GI Jahrestagung (1) 1986: 538-552 BibTeX

[36]

Michael Stonebraker, Timos K. Sellis, Eric N. Hanson: An Analysis of Rule Indexing Implementations in Data Base Systems. Expert Database Conf. 1986: 465-476 BibTeX

[37]

Michael Stonebraker, Lawrence A. Rowe: The Design of Postgres. SIGMOD Conference 1986: 340-355 BibTeX

[38]

...

[39]

...

Referenced by

1. Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
2. Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Networks and Network Computations. IEEE Trans. Knowl. Data Eng. 9(1): 102-119(1997)
3. Bruno Becker, Stephan Gschwind, Thomas Ohler, Bernhard Seeger, Peter Widmayer: An Asymptotically Optimal Multiversion B-Tree. VLDB J. 5(4): 264-275(1996)
4. Clive G. Page: Astronomical Tables, 2-D Indexing, and Fuzzy-joins. SSDBM 1996: 44-52
5. Maurício R. Mediano, Marco A. Casanova, Marcelo Dreux: V-Trees - A Storage Method for Long Vector Data. VLDB 1994: 321-330
6. Boris Novikov: Indices for Set-Theoretical Operations in Object Bases. ADBIS 1994: 208-216
7. Goetz Graefe: Query Evaluation Techniques for Large Databases. ACM Comput. Surv. 25(2): 73-170(1993)
8. Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526