Down the rabbit hole: Robust proximity search and density estimation in sublinear space?

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalArticlepeer-review

Abstract

For a set of n points in Rd , and parameters k and å, we present a data structure that answers (1 + å, k ) approximate nearest neighbor queries in logarithmic time. Surprisingly, the - space used by the data structure is O (n/k ), where the - O (•) notation here hides terms that are exponential in d, roughly varying as 1/åd ; as such, the space used is sublinear in the input size if k is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful proximity queries on the data can be carried out using this sketch. Using this, we provide a sublinear space data structure that can estimate the density of a point set under various measures, including (i) sum of distances of k closest points to the query point and (ii) sum of squared distances of k closest points to the query point. Our approach generalizes to other distance-based estimations of densities of similar flavor. We also study the problem of approximating some of these - quantities when using sampling. In particular, we show that a sample of size O (n/k ) is sufficient, in some restricted cases, to estimate the above quantities. Remarkably, the sample size has only linear dependency on the dimension. Copyright

Original languageEnglish (US)
Pages (from-to)1486-1511
Number of pages26
JournalSIAM Journal on Computing
Volume43
Issue number4
DOIs
StatePublished - 2014

Keywords

  • Approximate voronoi diagram
  • Geometricapproximation algorithms
  • K th nearest neighbor
  • Proximity search

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Down the rabbit hole: Robust proximity search and density estimation in sublinear space?'. Together they form a unique fingerprint.

Cite this