Multidimensional Access Methods.

Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)
  author    = {Volker Gaede and
               Oliver G{\"u}nther},
  title     = {Multidimensional Access Methods},
  journal   = {ACM Comput. Surv.},
  volume    = {30},
  number    = {2},
  year      = {1998},
  pages     = {170-231},
  ee        = {db/journals/csur/GaedeG98.html},
  bibsource = {DBLP,}


Search operations in databases require special support at the physical level. This is true for conventional databases as well as spatial databases, where typical search operations include the point query (find all objects that contain a given search point) and the region query (find all objects that overlap a given search region). More than ten years of spatial database research have resulted in a great variety of multidimensional access methods to support such operations. We give an overview of that work. After a brief survey of spatial data management in general, we first present the class of point access methods, which are used to search sets of points in two or more dimensions. The second part of the paper is devoted to spatial access methods to handle extended objects, such as rectangles or polyhedra. We conclude with a discussion of theoretical and experimental results concerning the relative performance of various approaches.

Copyright © 1998 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

Citation Page


[Abel and Mark 1990]
[Abel and Smith 1983]
[Ang and Tan 1997]
Chuan-Heng Ang, T. C. Tan: New Linear Node Splitting Algorithm for R-trees. SSD 1997: 339-349 BibTeX
[Aref and Samet 1994]
[Bayer 1996]
[Bayer and McCreight 1972]
Rudolf Bayer, Edward M. McCreight: Organization and Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189(1972) BibTeX
[Bayer and Schkolnick 1977]
Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX
[Becker et al. 1992]
Bruno Becker, Paolo Giulio Franciosa, Stephan Gschwind, Thomas Ohler, Gerald Thiemt, Peter Widmayer: Enclosing Many Boxes by an Optimal Pair of Boxes. STACS 1992: 475-486 BibTeX
[Becker 1992]
[Beckmann et al. 1990]
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
[Belussi and Faloutsos 1995]
Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310 BibTeX
[Bentley 1975]
Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975) BibTeX
[Bentley 1979]
Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979) BibTeX
[Bentley and Friedman 1979]
Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX
[Berchtold et al. 1996]
Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel: The X-tree : An Index Structure for High-Dimensional Data. VLDB 1996: 28-39 BibTeX
[Blanken et al. 1990]
Henk M. Blanken, Alle IJbema, Paul Meek, Bert van den Akker: The Generalized Grid File: Description and Performance Aspects. ICDE 1990: 380-388 BibTeX
[Brinkhoff 1994]
[Brinkhoff and Kriegel 1994]
Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179 BibTeX
[Brinkhoff et al. 1993a]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider: Comparison of Approximations of Complex Objects Used for Approximation-based Query Processing in Spatial Database Systems. ICDE 1993: 40-49 BibTeX
[Brinkhoff et al. 1993b]
Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246 BibTeX
[Brinkhoff et al. 1994]
Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208 BibTeX
[Brodsky et al. 1995]
Alexander Brodsky, Catherine Lassez, Jean-Louis Lassez, Michael J. Maher: Separability of Polyhedra for Optimal Filtering of Spatial and Constraint Data. PODS 1995: 54-65 BibTeX
[Burkhard 1984]
Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179 BibTeX
[Burkhard 1983]
Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983) BibTeX
[Chen et al. 1995]
Ling Tony Chen, R. Drach, M. Keating, S. Louis, Doron Rotem, Arie Shoshani: Efficient organization and access of multi-dimensional datasets on tertiary storage systems. Inf. Syst. 20(2): 155-183(1995) BibTeX
[Comer 1979]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX
[Dandamudi and Sorenson 1986]
Sivarama P. Dandamudi, Paul G. Sorenson: Algorithms for BD Trees. Softw., Pract. Exper. 16(12): 1077-1096(1986) BibTeX
[Dandamudi and Sorenson 1991]
Sivarama P. Dandamudi, Paul G. Sorenson: Improved Partial-Match Search Algorithms for BD Trees. Comput. J. 34(5): 415-422(1991) BibTeX
[Egenhofer 1989]
[Egenhofer 1994]
Max J. Egenhofer: Spatial SQL: A Query and Presentation Language. IEEE Trans. Knowl. Data Eng. 6(1): 86-95(1994) BibTeX
[Evangelidis 1994]
[Evangelidis et al. 1995]
Georgios Evangelidis, David B. Lomet, Betty Salzberg: The hBP-tree: A Modified hB-tree Supporting Concurrency, Recovery and Node Consolidation. VLDB 1995: 551-561 BibTeX
[Fagin et al. 1979]
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344(1979) BibTeX
[Faloutsos 1986]
Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238 BibTeX
[Faloutsos 1988]
Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988) BibTeX
[Faloutsos and Gaede 1996]
Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50 BibTeX
[Faloutsos and Kamel 1994]
Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13 BibTeX
[Faloutsos and Rong 1991]
Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159 BibTeX
[Faloutsos and Roseman 1989]
Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252 BibTeX
[Faloutsos et al. 1987]
Christos Faloutsos, Timos K. Sellis, Nick Roussopoulos: Analysis of Object Oriented Spatial Access Methods. SIGMOD Conference 1987: 426-439 BibTeX
[Finkel and Bentley 1974]
Raphael A. Finkel, Jon Louis Bentley: Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Inf. 4: 1-9(1974) BibTeX
[Flajolet 1983]
Philippe Flajolet: On the Performance Evaluation of Extendible Hashing and Trie Searching. Acta Inf. 20: 345-369(1983) BibTeX
[Frank and Barrera 1989]
Andrew U. Frank, Renato Barrera: The Fieldtree: A Data Structure for Geographic Information Systems. SSD 1989: 29-44 BibTeX
[Freeston 1987]
Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269 BibTeX
[Freeston 1989a]
Michael Freeston: Advances in the Design of the BANG File. FODO 1989: 322-338 BibTeX
[Freeston 1989b]
Michael Freeston: A Well-Behaved File Structure for the Storage of Spatial Objects. SSD 1989: 287-300 BibTeX
[Freeston 1995]
Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91 BibTeX
[Freeston 1997]
Michael Freeston: On the Complexity of BV-tree Updates. CDB 1997: 282-293 BibTeX
[Fuchs et al. 1983]
[Fuchs et al. 1980]
[Gaede 1995a]
Volker Gaede: Geometric Information Makes Spatial Query Processing More Efficient. ACM-GIS 1995: 45-52 BibTeX
[Gaede 1995b]
Volker Gaede: Optimal Redundancy in Spatial Database Systems. SSD 1995: 96-116 BibTeX
[Gaede and Riekert 1994]
Volker Gaede, Wolf-Fritz Riekert: Spatial Access Methods and Query Processing in the Object-Oriented GIS GODOT. AGDM 1994: 40- BibTeX
[Gaede and Wallace 1997]
Volker Gaede, Mark Wallace: An Informal Introduction to Constraint Database Systems. CDB 1997: 7-52 BibTeX
[Garg and Gotlieb 1986]
Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986) BibTeX
[Greene 1989]
Diane Greene: An Implementation and Performance Analysis of Spatial Data Access Methods. ICDE 1989: 606-615 BibTeX
[Günther 1988]
[Günther 1989]
Oliver Günther: The Design of the Cell Tree: An Object-Oriented Index Structure for Geometric Databases. ICDE 1989: 598-605 BibTeX
[Günther 1991]
[Günther 1993]
Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59 BibTeX
[Günther and Bilmes 1991]
Oliver Günther, Jeff Bilmes: Tree-Based Access Methods for Spatial Databases: Implementation and Performance Evaluation. IEEE Trans. Knowl. Data Eng. 3(3): 342-356(1991) BibTeX
[Günther and Buchmann 1990]
Oliver Günther, Alejandro P. Buchmann: Research Issues in Spatial Databases. SIGMOD Record 19(4): 61-68(1990) BibTeX
[Günther and Gaede 1997]
[Günther and Noltemeier 1991]
Oliver Günther, Hartmut Noltemeier: Spatial Database Indices for Large Extended Objects. ICDE 1991: 520-526 BibTeX
[Günther et al. 1997]
Oliver Günther, Rudolf Müller, Peter Schmidt, Hemant K. Bhargava, Ramayya Krishnan: MMM: A Web-Based System for Sharing Statistical Computing Modules. IEEE Internet Computing 1(3): 59-68(1997) BibTeX
[Günther et al. 1998]
Oliver Günther, Vincent Oria, Philippe Picouet, Jean-Marc Saglio, Michel Scholl: Benchmarking Spatial Joins À La Carte. SSDBM 1998: 32-41 BibTeX
[Güting 1989]
Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44 BibTeX
[Güting and Schneider 1993]
Ralf Hartmut Güting, Markus Schneider: Realms: A Foundation for Spatial Data Types in Database Systems. SSD 1993: 14-35 BibTeX
[Guttman 1984]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[Hellerstein et al. 1997]
Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256 BibTeX
[Hellerstein et al. 1995]
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573 BibTeX
[Henrich 1995]
Andreas Henrich: Adapting the Transformation Technique to Maintain Multi-Dimensional Non-Point Objects in k-d-Tree Based Access Structures. ACM-GIS 1995: 37-44 BibTeX
[Henrich and Möller 1995]
Andreas Henrich, Jens Möller: Extending a Spatial Access Structure to Support Additional Standard Attributes. SSD 1995: 132-151 BibTeX
[Henrich and Six 1991]
[Henrich et al. 1989]
Andreas Henrich, Hans-Werner Six, Peter Widmayer: The LSD tree: Spatial Access to Multidimensional Point and Nonpoint Objects. VLDB 1989: 45-53 BibTeX
[Hinrichs 1985]
Klaus Hinrichs: Implementation of the Grid File: Design Concepts and Experience. BIT 25(4): 569-592(1985) BibTeX
[Hoel and Samet 1992]
Erik G. Hoel, Hanan Samet: A Qualitative Comparison Study of Data Structures for Large Line Segment Databases. SIGMOD Conference 1992: 205-214 BibTeX
[Hoel and Samet 1995]
Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618 BibTeX
[Hutflesz et al. 1988a]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579 BibTeX
[Hutflesz et al. 1988b]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190 BibTeX
[Hutflesz et al. 1990]
Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: The R-File: An Efficient Access Structure for Proximity Queries. ICDE 1990: 372-379 BibTeX
[Hutflesz et al. 1991]
[Informix Inc. 1997]
[Jagadish 1990a]
H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342 BibTeX
[Jagadish 1990b]
H. V. Jagadish: On Indexing Line Segments. VLDB 1990: 614-625 BibTeX
[Jagadish 1990c]
H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319 BibTeX
[Kamel and Faloutsos 1992]
Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204 BibTeX
[Kamel and Faloutsos 1993]
Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499 BibTeX
[Kamel and Faloutsos 1994]
Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509 BibTeX
[Kamel et al. 1996]
[Kanellakis et al. 1993]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[Kedem 1982]
[Kemper and Wallrath 1987]
Alfons Kemper, Mechtild Wallrath: An Analysis of Geometric Modeling in Database Systems. ACM Comput. Surv. 19(1): 47-91(1987) BibTeX
[Klinger 1971]
[Knott 1975]
Gary D. Knott: Hashing Functions. Comput. J. 18(3): 265-278(1975) BibTeX
[Kolovson 1990]
[Kolovson and Stonebraker 1991]
Tim Connors, Waqar Hasan, Curtis P. Kolovson, Marie-Anne Neimat, Donovan A. Schneider, W. Kevin Wilkinson: The Papyrus Integrated Data Server. PDIS 1991: 139 BibTeX
[Kriegel 1984]
Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196 BibTeX
[Kriegel et al. 1991]
[Kriegel et al. 1990]
Hans-Peter Kriegel, Michael Schiwietz: Performance Comparison of Point and Spatial Access Methods. SSD 1989: 89-114 BibTeX
[Kriegel and Seeger 1986]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Order Preserving Linear Hashing with Partial Expansions. ICDT 1986: 203-220 BibTeX
[Kriegel and Seeger 1987]
Hans-Peter Kriegel, Bernhard Seeger: Multidimensional Dynamic Quantile Hashing is Very Efficient for Non-Uniform Record Distributions. ICDE 1987: 10-17 BibTeX
[Kriegel and Seeger 1988]
Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376 BibTeX
[Kriegel and Seeger 1989]
[Kornacker and Banks 1995]
Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145 BibTeX
[Kumar 1994a]
Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994) BibTeX
[Kumar 1994b]
Akhil Kumar: A Study of Spatial Clustering techniques. DEXA 1994: 57-71 BibTeX
[Larson 1980]
Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232 BibTeX
[Lehman and Yao 1981]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX
[Lin et al. 1994]
King-Ip Lin, H. V. Jagadish, Christos Faloutsos: The TV-Tree: An Index Structure for High-Dimensional Data. VLDB J. 3(4): 517-542(1994) BibTeX
[Litwin 1980]
Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223 BibTeX
[Lo and Ravishankar 1994]
Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220 BibTeX
[Lomet 1983]
David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX
[Lomet 1991]
David B. Lomet: Grow and Post Index Trees: Roles, Techniques and Future Potential. SSD 1991: 183-206 BibTeX
[Lomet and Salzberg 1989]
David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304 BibTeX
[Lomet and Salzberg 1990]
David B. Lomet, Betty Salzberg: The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance. ACM Trans. Database Syst. 15(4): 625-658(1990) BibTeX
[Lomet and Salzberg 1992]
David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360 BibTeX
[Lu and Ooi 1993]
Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993) BibTeX
[Matsuyama et al. 1994]
[Morton 1966]
[Nelson and Samet 1987]
Randal C. Nelson, Hanan Samet: A Population Analysis for Hierarchical Data Structures. SIGMOD Conference 1987: 270-277 BibTeX
[Newell and Doe 1997]
[Ng and Han 1994]
Raymond T. Ng, Jiawei Han: Efficient and Effective Clustering Methods for Spatial Data Mining. VLDB 1994: 144-155 BibTeX
[Ng and Kameda 1993]
Vincent Ng, Tiko Kameda: Concurrent Access to R-Trees. SSD 1993: 142-161 BibTeX
[Ng and Kameda 1994]
Vincent Ng, Tiko Kameda: The R-Link Tree: A Recoverable Index Structure for Spatial Data. DEXA 1994: 163-172 BibTeX
[Nievergelt 1989]
Jürg Nievergelt: 7 ± 2 Criteria for Assessing and Comparing Spatial data Structures. SSD 1989: 3-27 BibTeX
[Nievergelt and Hinrichs 1987]
Jürg Nievergelt, Klaus Hinrichs: Storage and Access Structures for Geometric Data Bases. FODO 1985: 441-455 BibTeX
[Nievergelt et al. 1981]
Jürg Nievergelt, Hans Hinterberger, Kenneth C. Sevcik: The Grid File: An Adaptable, Symmetric Multi-Key File Structure. ECI 1981: 236-251 BibTeX
[Nievergelt et al. 1984]
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
[Ohsawa and Sakauchi 1983]
Yutaka Ohsawa, Masao Sakauchi: The BD-Tree - A New N-Dimensional Data Structure with Highly Efficient Dynamic Characteristics. IFIP Congress 1983: 539-544 BibTeX
[Ohsawa and Sakauchi 1990]
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
[Ooi 1990]
[Ooi et al. 1987]
[Ooi et al. 1991]
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
[Oosterom 1990]
[Oracle inc. 1995]
[Orenstein 1982]
Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982) BibTeX
[Orenstein 1983]
Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141 BibTeX
[Orenstein 1989a]
Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305 BibTeX
[Orenstein 1989b]
Jack A. Orenstein: Strategies for Optimizing the Use of Redundancy in Spatial Databases. SSD 1989: 115-134 BibTeX
[Orenstein 1990]
Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352 BibTeX
[Orenstein and Merrett 1984]
Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190 BibTeX
[Orenstein 1986]
Jack A. Orenstein: Spatial Query Processing in an Object-Oriented Database System. SIGMOD Conference 1986: 326-336 BibTeX
[Otoo 1984]
Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506 BibTeX
[Otoo 1985]
[Otoo 1986]
Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113 BibTeX
[Ouksel 1985]
Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27 BibTeX
[Ouksel and Scheuermann 1983]
Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105 BibTeX
[Ouksel and Mayer 1992]
Aris M. Ouksel, Otto Mayer: A Robust and Efficient Spatial Data Structure. Acta Inf. 29(4): 335-373(1992) BibTeX
[Overmars et al. 1990]
Mark H. Overmars, Michiel H. M. Smid, Mark de Berg, Marc J. van Kreveld: Maintaining Range Trees in Secondary Memory. Part I: Partitions. Acta Inf. 27(5): 423-452(1989) BibTeX
[Pagel et al. 1993a]
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben: The Transformation Technique for Spatial Objects Revisited. SSD 1993: 73-88 BibTeX
[Pagel et al. 1995]
Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94 BibTeX
[Pagel et al. 1993b]
Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben, Peter Widmayer: Towards an Analysis of Range Query Performance in Spatial Data Structures. PODS 1993: 214-221 BibTeX
[Papadias et al. 1995]
Dimitris Papadias, Yannis Theodoridis, Timos K. Sellis, Max J. Egenhofer: Topological Relations in the World of Minimum Bounding Rectangles: A Study with R-trees. SIGMOD Conference 1995: 92-103 BibTeX
[Papadopoulos and Manolopoulos 1997]
Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408 BibTeX
[Peloux et al. 1994]
[Preparata and Shamos 1985]
Franco P. Preparata, Michael Ian Shamos: Computational Geometry - An Introduction. Springer 1985, ISBN 3-540-96131-3
[Regnier 1985]
Mireille Régnier: Analysis of Grid File Algorithms. BIT 25(2): 335-357(1985) BibTeX
[Robinson 1981]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[Rotem 1991]
Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509 BibTeX
[Roussopoulos Leifker 1984]
[Roussopoulos and Leifker 1985]
Nick Roussopoulos, Daniel Leifker: Direct Spatial Search on Pictorial Databases Using Packed R-Trees. SIGMOD Conference 1985: 17-31 BibTeX
[Sagan 1994]
[Samet 1984]
Hanan Samet: The Quadtree and Related Hierarchical Data Structures. ACM Comput. Surv. 16(2): 187-260(1984) BibTeX
[Samet 1988]
Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988) BibTeX
[Samet 1990a]
[Samet 1990b]
Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990
[Samet and Webber 1985]
Hanan Samet, Robert E. Webber: Storing a Collection of Polygons Using Quadtrees. ACM Trans. Graph. 4(3): 182-222(1985) BibTeX
[Schiwietz 1993]
Michael Schiwietz: Speicherung und Anfragebearbeitung komplexer Geo-Objekte. Ph.D. thesis, Ludwig-Maximilian-Universität München Verlag Shaker 1993, ISBN 3-86111-723-1
[Schneider and Kriegel 1992]
[Scholl and Voisard 1989]
Michel Scholl, Agnès Voisard: Thematic Map Modeling. SSD 1989: 167-190 BibTeX
[Seeger 1991]
Bernhard Seeger: Performance Comparison of Segment Access Methods Implemented on Top of the Buddy-Tree. SSD 1991: 277-296 BibTeX
[Seeger and Kriegel 1988]
Bernhard Seeger, Hans-Peter Kriegel: Techniques for Design and Implementation of Efficient Spatial Access Methods. VLDB 1988: 360-371 BibTeX
[Seeger and Kriegel 1990]
Bernhard Seeger, Hans-Peter Kriegel: The Buddy-Tree: An Efficient and Robust Access Method for Spatial Data Base Systems. VLDB 1990: 590-601 BibTeX
[Sellis et al. 1987]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[Sevcik and Koudas 1996]
Kenneth C. Sevcik, Nick Koudas: Filter Trees for Managing Spatial Data over a Range of Size Granularities. VLDB 1996: 16-27 BibTeX
[Sexton 1997]
Alan P. Sexton: Querying Indexed Files. CDB 1997: 263-281 BibTeX
[Shekhar and Liu 1995]
Shashi Shekhar, Duen-Ren Liu: CCAM: A Connectivity-Clustered Access Method for Aggregate Queries on Transportation Networks: A Summary of Results. ICDE 1995: 410-419 BibTeX
[Siemens Nixdorf Informationssysteme AG 1997]
[Six and Widmayer 1988]
Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503 BibTeX
[Smid and Overmars 1990]
Michiel H. M. Smid, Mark H. Overmars: Maintaining Range Trees in Secondary Memory. Part II: Lower Bounds. Acta Inf. 27(5): 453-480(1989) BibTeX
[Smith and Gao 1990]
[Stonebraker 1994]
Michael Stonebraker (Ed.): Readings in Database Systems, Second Edition. Morgan Kaufmann 1994, ISBN 1-55860-252-6
[Stonebraker et al. 1986]
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
[Stuckey 1997]
Peter J. Stuckey: Constraint Search Tree. ICLP 1997: 301-315 BibTeX
[Subramanian and Ramaswamy 1995]
Sairam Subramanian, Sridhar Ramaswamy: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. SODA 1995: 378-387 BibTeX
[Tamminen 1982]
Markku Tamminen: The Extendible Cell Method for Closest Point Problems. BIT 22(1): 27-41(1982) BibTeX
[Tamminen 1983]
[Tamminen 1984]
Markku Tamminen: Comment on Quad- and Octtrees. Commun. ACM 27(3): 248-249(1984) BibTeX
[Theodoridis and Sellis 1996]
Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171 BibTeX
[Tropf and Herzog 1981]
[Whang and Krishnamurthy 1985]
[White 1981]
[Widmayer 1991]

Referenced by

  1. Flip Korn, S. Muthukrishnan: Influence Sets Based on Reverse Nearest Neighbor Queries. SIGMOD Conference 2000: 201-212
  2. H. V. Jagadish, Nick Koudas, Divesh Srivastava: On Effective Multi-Dimensional Indexing for Strings. SIGMOD Conference 2000: 403-414
  3. Antonio Corral, Yannis Manolopoulos, Yannis Theodoridis, Michael Vassilakopoulos: Closest Pair Queries in Spatial Databases. SIGMOD Conference 2000: 189-200
  4. Pankaj K. Agarwal, Lars Arge, Jeff Erickson: Indexing Moving Points. PODS 2000: 175-186
  5. Caetano Traina Jr., Agma J. M. Traina, Bernhard Seeger, Christos Faloutsos: Slim-Trees: High Performance Metric Trees Minimizing Overlap Between Nodes. EDBT 2000: 51-65
  6. Zu-Kuan Wei, Young-Hwan Oh, Jae-dong Lee, Jae-Hong Kim, Dong-Sun Park, Young-Geol Lee, Hae-Young Bae: Efficient Spatial Transmission in Web-Based GIS. Workshop on Web Information and Data Management 1999: 38-42
  7. Elisa Bertino, Silvana Castano, Elena Ferrari, Marco Mesiti: Controlled Access and Dissemination of XML Documents. Workshop on Web Information and Data Management 1999: 22-27
  8. Marcel Kornacker: High-Performance Extensible Indexing. VLDB 1999: 699-708
  9. Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang: High Level Indexing of User-Defined Types. VLDB 1999: 554-564
  10. Nikos Mamoulis, Dimitris Papadias: Integration of Spatial Join Algorithms for Processing Multiple Inputs. SIGMOD Conference 1999: 1-12
  11. George Kollios, Dimitrios Gunopulos, Vassilis J. Tsotras: On Indexing Mobile Objects. PODS 1999: 261-272
  12. Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter: On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999: 346-357
  13. Joseph M. Hellerstein, Lisa Hellerstein, George Kollios: On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130
  14. Volker Markl, Martin Zirkel, Rudolf Bayer: Processing Operations with Restrictions in RDBMS without External Sorting: The Tetris Algorithm. ICDE 1999: 562-571
  15. Theodoros Tzouramanis, Michael Vassilakopoulos, Yannis Manolopoulos: Processing of Spatio-Temporal Queries in Image Databases. ADBIS 1999: 85-97
  16. Gunter Saake, Andreas Heuer: Datenbanken: Implementierungstechniken. MITP-Verlag 1999, ISBN 3-8266-0513-6
  17. Mihael Ankerst, Bernhard Braunmüller, Hans-Peter Kriegel, Thomas Seidl: Improving Adaptable Similarity Query Processing by Using Approximations. VLDB 1998: 206-217
  18. Yannis Theodoridis, Timos K. Sellis, Apostolos Papadopoulos, Yannis Manolopoulos: Specifications for Efficient Indexing in Spatiotemporal Databases. SSDBM 1998: 123-132
  19. Apostolos Papadopoulos, Yannis Manolopoulos: Multiple Range Query Optimization in Spatial Databases. ADBIS 1998: 71-82
  20. Daniel Barbará, William DuMouchel, Christos Faloutsos, Peter J. Haas, Joseph M. Hellerstein, Yannis E. Ioannidis, H. V. Jagadish, Theodore Johnson, Raymond T. Ng, Viswanath Poosala, Kenneth A. Ross, Kenneth C. Sevcik: The New Jersey Data Reduction Report. IEEE Data Eng. Bull. 20(4): 3-45(1997)
  21. Stéphane Grumbach, Philippe Rigaux, Michel Scholl, Luc Segoufin: DEDALE, A Spatial Constraint Database. DBPL 1997: 38-59
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (, Corrections:
DBLP: Copyright © by Michael Ley (, last change: Sat May 16 23:54:53 2009