Multidimensional Access Methods.

@article{DBLP:journals/csur/GaedeG98,
  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, http://dblp.uni-trier.de}
}

Abstract

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

• 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/An4-1 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

Online Edition: ACM Digital Library

References

[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

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

[Bayer and Schkolnick 1977]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977)

[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

[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

[Belussi and Faloutsos 1995]

Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310

[Bentley 1975]

Jon Louis Bentley: Multidimensional Binary Search Trees Used for Associative Searching. Commun. ACM 18(9): 509-517(1975)

[Bentley 1979]

Jon Louis Bentley: Multidimensional Binary Search Trees in Database Applications. IEEE Trans. Software Eng. 5(4): 333-340(1979)

[Bentley and Friedman 1979]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979)

[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

[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

[Brinkhoff 1994]

...

[Brinkhoff and Kriegel 1994]

Thomas Brinkhoff, Hans-Peter Kriegel: The Impact of Global Clustering on Spatial Database Systems. VLDB 1994: 168-179

[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

[Brinkhoff et al. 1993b]

Thomas Brinkhoff, Hans-Peter Kriegel, Bernhard Seeger: Efficient Processing of Spatial Joins Using R-Trees. SIGMOD Conference 1993: 237-246

[Brinkhoff et al. 1994]

Thomas Brinkhoff, Hans-Peter Kriegel, Ralf Schneider, Bernhard Seeger: Multi-Step Processing of Spatial Joins. SIGMOD Conference 1994: 197-208

[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

[Burkhard 1984]

Walter A. Burkhard: Index Maintenance for Non-Uniform Record Distributions. PODS 1984: 173-179

[Burkhard 1983]

Walter A. Burkhard: Interpolation-Based Index Maintenance. BIT 23(3): 274-294(1983)

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

[Comer 1979]

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

[Dandamudi and Sorenson 1986]

Sivarama P. Dandamudi, Paul G. Sorenson: Algorithms for BD Trees. Softw., Pract. Exper. 16(12): 1077-1096(1986)

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

[Egenhofer 1989]

...

[Egenhofer 1994]

Max J. Egenhofer: Spatial SQL: A Query and Presentation Language. IEEE Trans. Knowl. Data Eng. 6(1): 86-95(1994)

[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

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

[Faloutsos 1986]

Christos Faloutsos: Multiattribute Hashing Using Gray Codes. SIGMOD Conference 1986: 227-238

[Faloutsos 1988]

Christos Faloutsos: Gray Codes for Partial Match and Range Queries. IEEE Trans. Software Eng. 14(10): 1381-1393(1988)

[Faloutsos and Gaede 1996]

Christos Faloutsos, Volker Gaede: Analysis of n-Dimensional Quadtrees using the Hausdorff Fractal Dimension. VLDB 1996: 40-50

[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

[Faloutsos and Rong 1991]

Christos Faloutsos, Yi Rong: DOT: A Spatial Access Method Using Fractals. ICDE 1991: 152-159

[Faloutsos and Roseman 1989]

Christos Faloutsos, Shari Roseman: Fractals for Secondary Key Retrieval. PODS 1989: 247-252

[Faloutsos et al. 1987]

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

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

[Flajolet 1983]

Philippe Flajolet: On the Performance Evaluation of Extendible Hashing and Trie Searching. Acta Inf. 20: 345-369(1983)

[Frank and Barrera 1989]

Andrew U. Frank, Renato Barrera: The Fieldtree: A Data Structure for Geographic Information Systems. SSD 1989: 29-44

[Freeston 1987]

Michael Freeston: The BANG File: A New Kind of Grid File. SIGMOD Conference 1987: 260-269

[Freeston 1989a]

Michael Freeston: Advances in the Design of the BANG File. FODO 1989: 322-338

[Freeston 1989b]

Michael Freeston: A Well-Behaved File Structure for the Storage of Spatial Objects. SSD 1989: 287-300

[Freeston 1995]

Michael Freeston: A General Solution of the n-dimensional B-tree Problem. SIGMOD Conference 1995: 80-91

[Freeston 1997]

Michael Freeston: On the Complexity of BV-tree Updates. CDB 1997: 282-293

[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

[Gaede 1995b]

Volker Gaede: Optimal Redundancy in Spatial Database Systems. SSD 1995: 96-116

[Gaede and Riekert 1994]

Volker Gaede, Wolf-Fritz Riekert: Spatial Access Methods and Query Processing in the Object-Oriented GIS GODOT. AGDM 1994: 40-

[Gaede and Wallace 1997]

Volker Gaede, Mark Wallace: An Informal Introduction to Constraint Database Systems. CDB 1997: 7-52

[Garg and Gotlieb 1986]

Anil K. Garg, C. C. Gotlieb: Order-Preserving Key Transformations. ACM Trans. Database Syst. 11(2): 213-234(1986)

[Greene 1989]

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

[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

[Günther 1991]

...

[Günther 1993]

Oliver Günther: Efficient Computation of Spatial Joins. ICDE 1993: 50-59

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

[Günther and Buchmann 1990]

Oliver Günther, Alejandro P. Buchmann: Research Issues in Spatial Databases. SIGMOD Record 19(4): 61-68(1990)

[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

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

[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

[Güting 1989]

Ralf Hartmut Güting: Gral: An Extensible Relational Database System for Geometric Applications. VLDB 1989: 33-44

[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

[Guttman 1984]

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

[Hellerstein et al. 1997]

Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256

[Hellerstein et al. 1995]

Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573

[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

[Henrich and Möller 1995]

Andreas Henrich, Jens Möller: Extending a Spatial Access Structure to Support Additional Standard Attributes. SSD 1995: 132-151

[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

[Hinrichs 1985]

Klaus Hinrichs: Implementation of the Grid File: Design Concepts and Experience. BIT 25(4): 569-592(1985)

[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

[Hoel and Samet 1995]

Erik G. Hoel, Hanan Samet: Benchmarking Spatial Join Operations with Spatial Output. VLDB 1995: 606-618

[Hutflesz et al. 1988a]

Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Globally Order Preserving Multidimensional Linear Hashing. ICDE 1988: 572-579

[Hutflesz et al. 1988b]

Andreas Hutflesz, Hans-Werner Six, Peter Widmayer: Twin Grid Files: Space Optimizing Access Schemes. SIGMOD Conference 1988: 183-190

[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

[Hutflesz et al. 1991]

...

[Informix Inc. 1997]

...

[Jagadish 1990a]

H. V. Jagadish: Linear Clustering of Objects with Multiple Atributes. SIGMOD Conference 1990: 332-342

[Jagadish 1990b]

H. V. Jagadish: On Indexing Line Segments. VLDB 1990: 614-625

[Jagadish 1990c]

H. V. Jagadish: Spatial Search with Polyhedra. ICDE 1990: 311-319

[Kamel and Faloutsos 1992]

Ibrahim Kamel, Christos Faloutsos: Parallel R-trees. SIGMOD Conference 1992: 195-204

[Kamel and Faloutsos 1993]

Ibrahim Kamel, Christos Faloutsos: On Packing R-trees. CIKM 1993: 490-499

[Kamel and Faloutsos 1994]

Ibrahim Kamel, Christos Faloutsos: Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994: 500-509

[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

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

[Klinger 1971]

...

[Knott 1975]

Gary D. Knott: Hashing Functions. Comput. J. 18(3): 265-278(1975)

[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

[Kriegel 1984]

Hans-Peter Kriegel: Performance Comparison of Index Structures for Multi-Key Retrieval. SIGMOD Conference 1984: 186-196

[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

[Kriegel and Seeger 1986]

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

[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

[Kriegel and Seeger 1988]

Hans-Peter Kriegel, Bernhard Seeger: PLOP-Hashing: A Grid File without Directory. ICDE 1988: 369-376

[Kriegel and Seeger 1989]

...

[Kornacker and Banks 1995]

Marcel Kornacker, Douglas Banks: High-Concurrency Locking in R-Trees. VLDB 1995: 134-145

[Kumar 1994a]

Akhil Kumar: G-Tree: A New Data Structure for Organizing Multidimensional Data. IEEE Trans. Knowl. Data Eng. 6(2): 341-347(1994)

[Kumar 1994b]

Akhil Kumar: A Study of Spatial Clustering techniques. DEXA 1994: 57-71

[Larson 1980]

Per-Åke Larson: Linear Hashing with Partial Expansions. VLDB 1980: 224-232

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

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

[Litwin 1980]

Witold Litwin: Linear Hashing: A New Tool for File and Table Addressing. VLDB 1980: 212-223

[Lo and Ravishankar 1994]

Ming-Ling Lo, Chinya V. Ravishankar: Spatial Joins Using Seeded Trees. SIGMOD Conference 1994: 209-220

[Lomet 1983]

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983)

[Lomet 1991]

David B. Lomet: Grow and Post Index Trees: Roles, Techniques and Future Potential. SSD 1991: 183-206

[Lomet and Salzberg 1989]

David B. Lomet, Betty Salzberg: A Robust Multi-Attribute Search Structure. ICDE 1989: 296-304

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

[Lomet and Salzberg 1992]

David B. Lomet, Betty Salzberg: Access Method Concurrency with Recovery. SIGMOD Conference 1992: 351-360

[Lu and Ooi 1993]

Hongjun Lu, Beng Chin Ooi: Spatial Indexing: Past and Future. IEEE Data Eng. Bull. 16(3): 16-21(1993)

[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

[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

[Ng and Kameda 1993]

Vincent Ng, Tiko Kameda: Concurrent Access to R-Trees. SSD 1993: 142-161

[Ng and Kameda 1994]

Vincent Ng, Tiko Kameda: The R-Link Tree: A Recoverable Index Structure for Spatial Data. DEXA 1994: 163-172

[Nievergelt 1989]

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

[Nievergelt and Hinrichs 1987]

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

[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

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

[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

[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

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

[Oosterom 1990]

...

[Oracle inc. 1995]

...

[Orenstein 1982]

Jack A. Orenstein: Multidimensional Tries Used for Associative Searching. Inf. Process. Lett. 14(4): 150-157(1982)

[Orenstein 1983]

Jack A. Orenstein: A Dynamic Hash File for Random and Sequential Accessing. VLDB 1983: 132-141

[Orenstein 1989a]

Jack A. Orenstein: Redundancy in Spatial Databases. SIGMOD Conference 1989: 295-305

[Orenstein 1989b]

Jack A. Orenstein: Strategies for Optimizing the Use of Redundancy in Spatial Databases. SSD 1989: 115-134

[Orenstein 1990]

Jack A. Orenstein: A Comparison of Spatial Query Processing Techniques for Native and Parameter Spaces. SIGMOD Conference 1990: 343-352

[Orenstein and Merrett 1984]

Jack A. Orenstein, T. H. Merrett: A Class of Data Structures for Associative Searching. PODS 1984: 181-190

[Orenstein 1986]

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

[Otoo 1984]

Ekow J. Otoo: A Mapping Function for the Directory of a Multidimensional Extendible Hashing. VLDB 1984: 493-506

[Otoo 1985]

...

[Otoo 1986]

Ekow J. Otoo: Balanced Multidimensional Extendible Hash Tree. PODS 1986: 100-113

[Ouksel 1985]

Aris M. Ouksel: The Interpolation-Based Grid File. PODS 1985: 20-27

[Ouksel and Scheuermann 1983]

Aris M. Ouksel, Peter Scheuermann: Storage Mappings for Multidimensional Linear Dynamic Hashing. PODS 1983: 90-105

[Ouksel and Mayer 1992]

Aris M. Ouksel, Otto Mayer: A Robust and Efficient Spatial Data Structure. Acta Inf. 29(4): 335-373(1992)

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

[Pagel et al. 1993a]

Bernd-Uwe Pagel, Hans-Werner Six, Heinrich Toben: The Transformation Technique for Spatial Objects Revisited. SSD 1993: 73-88

[Pagel et al. 1995]

Bernd-Uwe Pagel, Hans-Werner Six, Mario Winter: Window Query-Optimal Clustering of Spatial Objects. PODS 1995: 86-94

[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

[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

[Papadopoulos and Manolopoulos 1997]

Apostolos Papadopoulos, Yannis Manolopoulos: Performance of Nearest Neighbor Queries in R-Trees. ICDT 1997: 394-408

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

[Robinson 1981]

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

[Rotem 1991]

Doron Rotem: Spatial Join Indices. ICDE 1991: 500-509

[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

[Sagan 1994]

...

[Samet 1984]

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

[Samet 1988]

Hanan Samet: Hierarchical Representations of Collections of Small Rectangles. ACM Comput. Surv. 20(4): 271-309(1988)

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

[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

[Seeger 1991]

Bernhard Seeger: Performance Comparison of Segment Access Methods Implemented on Top of the Buddy-Tree. SSD 1991: 277-296

[Seeger and Kriegel 1988]

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

[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

[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

[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

[Sexton 1997]

Alan P. Sexton: Querying Indexed Files. CDB 1997: 263-281

[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

[Siemens Nixdorf Informationssysteme AG 1997]

...

[Six and Widmayer 1988]

Hans-Werner Six, Peter Widmayer: Spatial Searching in Geometric Databases. ICDE 1988: 496-503

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

[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

[Stuckey 1997]

Peter J. Stuckey: Constraint Search Tree. ICLP 1997: 301-315

[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

[Tamminen 1982]

Markku Tamminen: The Extendible Cell Method for Closest Point Problems. BIT 22(1): 27-41(1982)

[Tamminen 1983]

...

[Tamminen 1984]

Markku Tamminen: Comment on Quad- and Octtrees. Commun. ACM 27(3): 248-249(1984)

[Theodoridis and Sellis 1996]

Yannis Theodoridis, Timos K. Sellis: A Model for the Prediction of R-tree Performance. PODS 1996: 161-171

[Tropf and Herzog 1981]

...

[Whang and Krishnamurthy 1985]

...

[White 1981]

...

[Widmayer 1991]

...