Graph-Based Nearest-Neighbor Search without the Spread

$$Recent work showed how to construct nearest-neighbor graphs of linear size, on a given set $P$ of $n$ points in ${\mathrm{\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$.