(\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).