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.

该研究介绍了一种名为优先的动态连续索引（Prioritized DCI）的变体，用于 k 近邻搜索，并且相对于现有方法（如局部敏感哈希，LSH），优先 DCI 通过线性增加空间而不是查询时间的依赖来解决了维数灾难的问题，并在内在维数方面展现了显着的改进。