E. Koutsoupias and D. S. Taylor.

**Tight bounds for 2-dimensional indexing schemes.**In*Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems*, Seattle, Washington, June 1--4, 1998.### Abstract

We study the trade-off between storage redundancy and access overhead for range queries, using the framework of Hellerstein, Koutsoupias, andPapadimitriou [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.

### Bib

@string{PODS98 = {Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems}} @InProceedings{KT98, author = {E. Koutsoupias and D. S. Taylor}, title = {Tight bounds for 2-dimensional indexing schemes}, booktitle = PODS98, address= {Seattle, Washington}, month = {1--4 } # jun, year = 1998 }