Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space

Sariel Har-Peled, Nirman Kumar

For a set of $n$ points in ${\Re }^d$, and parameters $k$ and $\eps$, we present a data structure that answers $(1+\eps,k)$-\ANN queries in logarithmic time. Surprisingly, the space u…