For a set of n points in R^{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 O(n /k); that is, 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 estimation of densities of similar flavor.

PDF.
PDF slides.
Last modified: Tue Nov 6 11:14:14 CST 2012