On Two-Dimensional Indexability and Optimal Range Search Indexing.

@inproceedings{DBLP:conf/pods/ArgeSV99,
  author    = {Lars Arge and
               Vasilis Samoladas and
               Jeffrey Scott Vitter},
  title     = {On Two-Dimensional Indexability and Optimal Range Search Indexing},
  booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1999},
  isbn      = {1-58113-062-7},
  pages     = {346-357},
  ee        = {http://doi.acm.org/10.1145/303976.304010, db/conf/pods/ArgeSV99.html},
  crossref  = {DBLP:conf/pods/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1999 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 DiSC

• 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/DISC001 or /cdrom

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 DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

Online Edition: ACM Digital Library

References

[1]

Pankaj K. Agarwal, Lars Arge, Jeff Erickson, Paolo Giulio Franciosa, Jeffrey Scott Vitter: Efficient Searching with Linear Constraints. PODS 1998: 169-178

[2]

...

[3]

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

[4]

...

[5]

Bernard Chazelle: Filtering Search: A New Approach to Query-Answering. SIAM J. Comput. 15(3): 703-724(1986)

[6]

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

[7]

Volker Gaede, Oliver Günther: Multidimensional Access Methods. ACM Comput. Surv. 30(2): 170-231(1998)

[8]

...

[9]

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

[10]

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

[11]

Scott Huddleston, Kurt Mehlhorn: A New Data Structure for Representing Sorted Lists. Acta Inf. 17: 157-184(1982)

[12]

Christian Icking, Rolf Klein, Thomas Ottmann: Priority Search Trees in Secondary Memory (Extended Abstract). WG 1987: 84-93

[13]

Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. J. Comput. Syst. Sci. 52(3): 589-612(1996)

[14]

Elias Koutsoupias, David Scot Taylor: Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998: 52-58

[15]

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)

[16]

Edward M. McCreight: Priority Search Trees. SIAM J. Comput. 14(2): 257-276(1985)

[17]

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)

[18]

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

[19]

Mark H. Overmars: The Design of Dynamic Data Structures. Lecture Notes in Computer Science Vol. 156 Springer 1983, ISBN 3-540-12330-X

[20]

Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35

[21]

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

[22]

...

[23]

Hanan Samet: The Design and Analysis of Spatial Data Structures. Addison-Wesley 1990

[24]

Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51

[25]

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

[26]

Sairam Subramanian, Sridhar Ramaswamy: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. SODA 1995: 378-387

[27]

...

[28]

Darren Erik Vengroff, Jeffrey Scott Vitter: Efficient 3-D Range Searching in External Memory. STOC 1996: 192-201

[29]

...