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 by avoiding space partitioning and achieves a query time that grows sublinearly in the intrinsic dimensionality. In this paper, we develop a variant of DCI, which we call Prioritized DCI, and show a further improvement in the dependence on the intrinsic dimensionality compared to standard DCI, thereby improving the performance of DCI on datasets with high intrinsic dimensionality. We also demonstrate empirically that Prioritized DCI compares favourably to standard DCI and Locality-Sensitive Hashing (LSH) both in terms of running time and space consumption at all levels of approximation quality. In particular, relative to LSH, Prioritized DCI reduces the number of distance evaluations by a factor of 5 to 30 and the space consumption by a factor of 47 to 55.

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

基于优先的DCI的快速k近邻搜索