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

Sariel Har-Peled, Nirman Kumar

Research output: Contribution to journalConference articlepeer-review

Abstract

For a set of n points in ℝd, and parameters k and ε, we present a data structure that answers (1 + ε)-approximate k nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data-structure is Õ(n/k), that is, the space used is sub linear 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 sub linear 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 estimation of densities of similar flavor.

Original languageEnglish (US)
Article number6375321
Pages (from-to)430-439
Number of pages10
JournalProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
DOIs
StatePublished - Dec 1 2012
Event53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012 - New Brunswick, NJ, United States
Duration: Oct 20 2012Oct 23 2012

ASJC Scopus subject areas

  • Computer Science(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