Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space
Sariel Har-Peled, Nirman Kumar · SIAM Journal on Computing · 2014
For a set of $n$ points in $\mathbb{R}^d$, and parameters $k$ and $\varepsilon$, we present a data structure that answers $(1+\varepsilon,k)$ approximate nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data structure is $\widetilde{O}(n /k)$, where the $\widetilde{O}(\cdot)$ notation here hides terms that are exponential in $d$, roughly varying as $1/\varepsilon^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 $\widetilde{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.