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

Tight Bounds for 2-Dimensional Indexing Schemes.

Elias Koutsoupias, David Scot Taylor: Tight Bounds for 2-Dimensional Indexing Schemes. PODS 1998: 52-58
@inproceedings{DBLP:conf/pods/KoutsoupiasT98,
  author    = {Elias Koutsoupias and
               David Scot Taylor},
  title     = {Tight Bounds for 2-Dimensional Indexing Schemes},
  booktitle = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, June 1-3, 1998, Seattle, Washington},
  publisher = {ACM Press},
  year      = {1998},
  isbn      = {0-89791-996-3},
  pages     = {52-58},
  ee        = {http://doi.acm.org/10.1145/275487.275494, db/conf/pods/KoutsoupiasT98.html},
  crossref  = {DBLP:conf/pods/98},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

We study the trade-off between storage redundancy and access overhead for range queries, using the framework of [Hellerstein,Koutsoupias,Papadimitriou, PODS97]. We show that the Fibonacci workload of size n, which is the regular 2-dimensional grid rotated by the golden ratio, does not admit an indexing scheme with access overhead less than the block size B (the worst possible access overhead), even for storage redundancy as high as c*log n, for some constant c. We also show that this bound is tight (up to a constant factor) by providing an indexing scheme with storage redundancy Theta(log n) and constant access overhead, for any 2-dimensional workload. We extend the lower bound to random point sets and show that if the maximum storage redundancy is less than c*loglog n, the access overhead is B. Finally, we explore the relation between indexability and fractal (Hausdorff) dimension of point sets.

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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 1-3, 1998, Seattle, Washington. ACM Press 1998, ISBN 0-89791-996-3
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 849 KB]

References

[1]
Alberto Belussi, Christos Faloutsos: Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension. VLDB 1995: 299-310 BibTeX
[2]
Benny Chor, Charles E. Leiserson, Ronald L. Rivest, James B. Shearer: An application of number theory to the organization of raster-graphics memory. J. ACM 33(1): 86-104(1986) BibTeX
[3]
Christos Faloutsos, Ibrahim Kamel: Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension. PODS 1994: 4-13 BibTeX
[4]
...
[5]
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching. SIGMOD Conference 1984: 47-57 BibTeX
[6]
Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou: On the Analysis of Indexing Schemes. PODS 1997: 249-256 BibTeX
[7]
Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer: Generalized Search Trees for Database Systems. VLDB 1995: 562-573 BibTeX
[8]
...
[9]
Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, Jeffrey Scott Vitter: Indexing for Data Models with Constraints and Classes. PODS 1993: 233-243 BibTeX
[10]
Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX
[11]
Nathan Linial, Michael Luby, Michael E. Saks, David Zuckerman: Efficient construction of a small hitting set for combinatorial rectangles in high dimension. STOC 1993: 258-267 BibTeX
[12]
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
[13]
...
[14]
Sridhar Ramaswamy, Paris C. Kanellakis: OODB Indexing by Class-Division. SIGMOD Conference 1995: 139-150 BibTeX
[15]
Sridhar Ramaswamy, Sairam Subramanian: Path Caching: A Technique for Optimal External Searching. PODS 1994: 25-35 BibTeX
[16]
John T. Robinson: The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes. SIGMOD Conference 1981: 10-18 BibTeX
[17]
Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51 BibTeX
[18]
...
[19]
Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos: The R+-Tree: A Dynamic Index for Multi-Dimensional Objects. VLDB 1987: 507-518 BibTeX
[20]
...
[21]
...

Referenced by

  1. Lars Arge, Vasilis Samoladas, Jeffrey Scott Vitter: On Two-Dimensional Indexability and Optimal Range Search Indexing. PODS 1999: 346-357
  2. Kothuri Venkata Ravi Kanth, Ambuj K. Singh: Optimal Dynamic Range Searching in Non-replicating Index Structures. ICDT 1999: 257-276
  3. Joseph M. Hellerstein, Lisa Hellerstein, George Kollios: On the Generation of 2-Dimensional Index Workloads. ICDT 1999: 113-130
  4. Vasilis Samoladas, Daniel P. Miranker: A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries. PODS 1998: 44-51
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:18 2009