algorithm - 超大维度的 k-NN 搜索（~100,000）

Question

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

大多数对真实世界数据进行测试的文章都使用 10-50 暗淡，少数文章使用 100-500。

在我的情况下，在 ~100k 特征维度中有 ~10^9 个点，并且没有办法有效地减少维数。

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

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

Answer 1

看看FLANN库。

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

Answer 2

您是否使用 kd-tree 进行最近邻搜索？kd-tree 在更高维度上退化为几乎穷举搜索。

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

在最近邻搜索方面，有许多因素会影响决策的选择。您是否需要将这些点完全加载到主内存中，或者您可以使用辅助内存也应该决定您的决定。