Tight bounds for 2-dimensional indexing schemes
Elias Koutsoupias, David Scot Taylor · 1998
We study the trade-off between storage redundancy and access overhead for range queries, using the framework of [6]. 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 cloglog n, the access overhead is B. Finally, we explore the relation between indexability and fractal (Hausdorff) dimension of point sets. 1 Introduction In this paper we continue the work of [6] towards a theory of indexability ---that is, towards a better understandin...