E. Koutsoupias and D. S. Taylor.
Indexing schemes for random points.
In Proceedings of the 10th Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 596--602, Baltimore, Maryland,
17--19 January 1999.
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.Bib
@string{SODA99 = {Proceedings of the 10th Annual ACM-SIAM Symposium on
Discrete Algorithms}}
@InProceedings{KT99,
author = {E. Koutsoupias and D. S. Taylor},
title = {Indexing schemes for random points},
booktitle = SODA99,
year = 1999,
month = {17--19 } # jan,
pages = {596--602},
address = {Baltimore, Maryland},
}