Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784

phone: +30 210 7275122
fax: +30 210 7275114

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.
Download: pdf ps


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.


@string{SODA99 = {Proceedings of the 10th Annual ACM-SIAM Symposium on 
		  Discrete Algorithms}}

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