最近邻的一些快速近似有哪些？
假设我有一个巨大的（几百万）n 个向量列表，给定一个新向量，我需要从集合中找到一个非常接近的向量，但它不需要是最接近的。 （最近邻找到最接近的并运行 n 次）
有哪些算法可以非常快速地逼近最近邻，但牺牲了准确性？
编辑：因为它可能会有所帮助，所以我应该提到数据在大多数情况下都非常平滑，在随机维度上出现尖峰的可能性很小。
Say I have a huge (a few million) list of n vectors, given a new vector, I need to find a pretty close one from the set but it doesn't need to be the closest. (Nearest Neighbor finds the closest and runs in n time)
What algorithms are there that can approximate nearest neighbor very quickly at the cost of accuracy?
EDIT: Since it will probably help, I should mention the data are pretty smooth most of the time, with a small chance of spikiness in a random dimension.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
存在比 O(n) 更快的算法来通过任意距离搜索最近的元素。有关详细信息，请查看 http://en.wikipedia.org/wiki/Kd-tree。
There are exist faster algoritms then O(n) to search closest element by arbitary distance. Check http://en.wikipedia.org/wiki/Kd-tree for details.
如果您使用高维向量，例如 SIFT 或 SURF 或多媒体领域使用的任何描述符，我建议您考虑 LSH。
魏东的博士论文 (http://www.cs.princeton.edu/ cass/papers/cikm08.pdf）可能会帮助您找到KNN搜索的更新算法，即LSH。与更传统的 LSH 不同，例如 E2LSH (http://www.mit.edu/~andoni/LSH /）由麻省理工学院的研究人员早些时候发表，他的算法使用多重探测来更好地平衡召回率和成本之间的权衡。
If you are using high-dimension vector, like SIFT or SURF or any descriptor used in multi-media sector, I suggest your consider LSH.
A PhD dissertation from Wei Dong (http://www.cs.princeton.edu/cass/papers/cikm08.pdf) might help you find the updated algorithm of KNN search, i.e, LSH. Different from more traditional LSH, like E2LSH (http://www.mit.edu/~andoni/LSH/) published earlier by MIT researchers, his algorithm uses multi-probing to better balance the trade-off between recall rate and cost.
对“最近邻居”lsh 库的网络搜索发现
http://www.mit.edu/~andoni/LSH/
http://www.cs.umd.edu/~mount/ANN/
http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN .htm
A web search on "nearest neighbor" lsh library finds
http://www.mit.edu/~andoni/LSH/
http://www.cs.umd.edu/~mount/ANN/
http://msl.cs.uiuc.edu/~yershova/MPNN/MPNN.htm
对于近似最近邻，最快的方法是使用局部敏感哈希（LSH）。 LSH 有多种变体。您应该根据数据的距离度量来选择一种。 LSH 查询时间的 big-O 与数据集大小无关（不考虑输出结果的时间）。所以它真的很快。这个LSH库实现了L2（欧几里德）空间的各种LSH。
现在，如果您的数据维度小于 10，则首选 kd 树想要准确的结果。
For approximate nearest neighbour, the fastest way is to use locality sensitive hashing (LSH). There are many variants of LSHs. You should choose one depending on the distance metric of your data. The big-O of the query time for LSH is independent of the dataset size (not considering time for output result). So it is really fast. This LSH library implements various LSH for L2 (Euclidian) space.
Now, if the dimension of your data is less than 10, kd tree is preferred if you want exact result.