 |
|
|
Tight Bounds for 2-Dimensional Indexing Schemes |
Full Paper (PDF)
|
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. |
References, where available, link to the DBLP on the World Wide Web.
[1]Alberto Belussi, Christos Faloutsos:
Estimating the Selectivity of Spatial Queries Using the `Correlation' Fractal Dimension.
VLDB 1995: 299-310[2]Benny Chor, Charles E. Leiserson, Ronald L. Rivest, James B. Shearer:
An Application for Number Theory to the Organization of Raster-Graphics Memory.
JACM 33(1): 86-104(1986)[3]Christos Faloutsos, Ibrahim Kamel:
Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension.
PODS 1994: 4-13[4]...
[5]Antonin Guttman:
R-Trees: A Dynamic Index Structure for Spatial Searching.
SIGMOD Conference 1984: 47-57[6]Joseph M. Hellerstein, Elias Koutsoupias, Christos H. Papadimitriou:
On the Analysis of Indexing Schemes.
PODS 1997: 249-256[7]Joseph M. Hellerstein, Jeffrey F. Naughton, Avi Pfeffer:
Generalized Search Trees for Database Systems.
VLDB 1995: 562-573[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[10]Donald E. Knuth:
The Art of Computer Programming, Volume III: Sorting and Searching.
Addison-Wesley 1973, ISBN 0-201-03803-X
[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[12]David B. Lomet, Betty Salzberg:
The hB-Tree: A Multiattribute Indexing Method with Good Guaranteed Performance.
TODS 15(4): 625-658(1990)[13]...
[14]Sridhar Ramaswamy, Paris C. Kanellakis:
OODB Indexing by Class-Division.
SIGMOD Conference 1995: 139-150[15]Sridhar Ramaswamy, Sairam Subramanian:
Path Caching: A Technique for Optimal External Searching.
PODS 1994: 25-35[16]John T. Robinson:
The K-D-B-Tree: A Search Structure For Large Multidimensional Dynamic Indexes.
SIGMOD Conference 1981: 10-18[17]Vasilis Samoladas, Daniel P. Miranker:
A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries.
PODS 1998: 44-51[18]...
[19]Timos K. Sellis, Nick Roussopoulos, Christos Faloutsos:
The R+-Tree: A Dynamic Index for Multi-Dimensional Objects.
VLDB 1987: 507-518[20]...
[21]...
Referenced By:
- Vasilis Samoladas, Daniel P. Miranker:
A Lower Bound Theorem for Indexing Schemes and Its Application to Multidimensional Range Queries.
PODS 1998: 44-51
|
@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-966-3},
pages = {52-58},
crossref = {DBLP:conf/pods/98},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
|
DBLP: Copyright ©1999 by Michael Ley (ley@uni-trier.de).
|
|
