Graph-Based Nearest-Neighbor Search without the Spread
This addresses a theoretical limitation in graph-based nearest-neighbor search for computational geometry, though it appears incremental as it builds on prior work to improve time complexity.
The authors tackled the problem of removing the dependency on the spread in nearest-neighbor graphs for approximate nearest-neighbor search, achieving query times logarithmic in the number of points rather than the spread.
$\renewcommand{\Re}{\mathbb{R}}$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in $\Re^d$, such that one can answer approximate nearest-neighbor queries in logarithmic time in the spread. Unfortunately, the spread might be unbounded in $n$, and an interesting theoretical question is how to remove the dependency on the spread. Here, we show how to construct an external linear-size data structure that, combined with the linear-size graph, allows us to answer ANN queries in logarithmic time in $n$.