Abstract:

We investigate the tradeoff between storage redundancy and access overhead for indexing random d-dimensional point sets. We show that with high probability a range-query workload of n random points has polylogarithmic trade-off; more precisely, there is a constant c_{B,d} such that every indexing scheme with storage redundancy c_{B,d}\log^{d-1} n has the worst possible access overhead (equal to the block size B). We also show that this result is almost tight and that the trade-off even exhibits a threshold behavior: on a random set of points, expected storage redundancy O(\log^{d-1} n) achieves access overhead 2d-1.

Postscript

Pdf

BibTeX