algorithm - 最近邻的一些快速近似值是什么？

Question

假设我有一个巨大的（几百万）n 个向量列表，给定一个新向量，我需要从集合中找到一个非常接近的向量，但它不需要是最接近的。（Nearest Neighbor 找到最近的并在 n 时间内运行）

有哪些算法可以以准确性为代价快速逼近最近邻？

编辑：因为它可能会有所帮助，我应该提到数据在大多数情况下都非常平滑，随机维度中出现尖峰的可能性很小。

Answer 1

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

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/ )，他的算法使用多重探测来更好地平衡召回率和成本之间的权衡。

Answer 3

在“最近的邻居”lsh 库上的网络搜索发现 h​​ttp: //www.mit.edu/~andoni/LSH/ http://www.cs.umd.edu/~mount/ANN/ http://msl.cs .uiuc.edu/~yershova/MPNN/MPNN.htm

Answer 4

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

现在，如果您的数据维度小于 10，如果您想要精确的结果，则首选kd 树。