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.

Postscript

Pdf

BibTeX