最近邻的一些快速近似算法是什么？

Question

假设我有一个由n个向量组成的巨大列表（几百万个），给定一个新向量，我需要从该集合中找到一个相当接近的向量，但不一定是最接近的。（最近邻算法可以找到最接近的向量，但时间复杂度为n）

有哪些算法可以以很快的速度近似查找最近邻，但代价是准确性？

编辑：因为这可能会有所帮助，我应该提到数据大部分时间都很平滑，在随机维度上有小概率出现尖峰。

- Nathan

---

向量的维度是多少？你使用的距离函数是什么？ - Aryabhatta

5维的。我只是使用勾股定理的概括。 - Nathan

这份调查可能会有用：http://www.almaden.ibm.com/u/kclarkson/nn_survey/p.pdf - Aryabhatta

Answer 1

存在比O(n)更快的算法来通过任意距离搜索最接近的元素。详见http://en.wikipedia.org/wiki/Kd-tree。

- yura

---

+1 我本来想建议使用kd树。它可以找到最近的邻居，也可以在O(log(n)+k)的时间内找到k个最近的邻居。 - phkahler

如果您在查看了1000个1m点后就退出，KD树会快得多。请参见cutoff 1000, 5000的运行时间，以及有关LSH的好链接。 - denis

Answer 2

如果您正在使用高维向量，例如SIFT或SURF或多媒体领域中使用的任何描述符，我建议您考虑LSH。

魏东的博士论文（http://www.cs.princeton.edu/cass/papers/cikm08.pdf）可能会帮助您找到更新的KNN搜索算法，即LSH。与传统的LSH（例如MIT研究人员早期发表的E2LSH（http://www.mit.edu/~andoni/LSH/））不同，他的算法使用多探测来更好地平衡召回率和成本之间的权衡。

- HMK

Answer 3

对于近似最近邻，最快的方法是使用局部敏感哈希（LSH）。有许多LSH变体。您应根据数据的距离度量选择其中一种。 LSH的查询时间的大O与数据集大小无关（不考虑输出结果的时间）。因此它非常快。这个LSH库实现了各种L2（欧几里得）空间的LSH。

现在，如果您的数据维数小于10，则优先使用kd tree以获得精确结果。

- ekzhu

Answer 4

在网上搜索“最近邻”lsh库会发现以下链接： http://www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm

- mcdowella