  Most exact methods for k-nearest neighbour search suffer from the curse of
dimensionality; that is, their query times exhibit exponential dependence on
either the ambient or the intrinsic dimensionality. Dynamic Continuous Indexing
(DCI) offers a promising way of circumventing the curse and successfully
reduces the dependence of query time on intrinsic dimensionality from
exponential to sublinear. In this paper, we propose a variant of DCI, which we
call Prioritized DCI, and show a remarkable improvement in the dependence of
query time on intrinsic dimensionality. In particular, a linear increase in
intrinsic dimensionality, or equivalently, an exponential increase in the
number of points near a query, can be mostly counteracted with just a linear
increase in space. We also demonstrate empirically that Prioritized DCI
significantly outperforms prior methods. In particular, relative to
Locality-Sensitive Hashing (LSH), Prioritized DCI reduces the number of
distance evaluations by a factor of 14 to 116 and the memory consumption by a
factor of 21.
