Elias Koutsoupias / Publications

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.

@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
}