k-NN海量搜索(约100,000)

Question

有没有像10k - 100k这样的海量维度的k-NN搜索问题的文章？

大多数对真实世界数据进行测试的文章都是在10-50维度下运行的，少数文章是在100-500级别运行的。

在我的例子中，大约100k特征维度中有大约10^9个点，并且没有办法有效地减少维度的数量。

更新:目前我们正在尝试调整和实现VP-trees，但很明显，在这个维度上的任何树结构都不会很好地工作。

第二种方法是LSH，但是依赖于数据分布的准确性可能会有很大的问题。

Answer 1

看一看FLANN库。

在this paper中，您可以找到一篇关于数据维度如何成为对最近邻匹配性能有很大影响的因素之一的论文，以及FLANN中采用的解决方案。

Answer 2

您是否正在使用kd-tree进行最近邻搜索？kd-tree在更高的维度上恶化到几乎穷尽的搜索。

在更高的维度中，通常建议使用近似最近邻搜索。这是到原始论文的链接: dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt‎，如果这有点太重，可以试试这个：http://cvs.cs.umd.edu/~mount/Papers/dist.pdf。

当涉及到最近邻搜索时，有许多因素影响决策的选择。您是否需要将点完全加载到主内存中，还是可以使用辅助内存，这也应该决定您的决定。