什么是最近邻的快速近似？

Question

假设我有一个巨大的（几百万）n个向量的列表，给定一个新的向量，我需要找到一个非常接近的集合，但它不需要是最接近的。 （最近邻居发现最近并且运行n次）

哪些算法能够以精度为代价非常快地近似最近邻居？

编辑：既然它可能会有所帮助，我应该提及的数据大多数时间都很顺利，随机维度中出现尖刺的可能性很小。

Answer 1

有存在更快algoritms然后为O（n ）通过任意距离搜索最接近的元素。详情请查询http://en.wikipedia.org/wiki/Kd-tree。

Answer 2

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

Answer 3

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

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

Answer 4

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

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