快速查找给定向量的字典向量.高尺寸

Question

我正在寻找可扩展的答案,但出于我的特定目的,我有一个48维向量.这可以表示为48个整数的数组,全部介于0和255之间.

我有一本关于这些载体的大字典,大约有2.5万个.

我需要能够获取可能在我的数据库中或可能不在我的数据库中的向量,并快速找到数据库中哪个向量最接近.最接近,我的意思是传统的距离公式.

我的代码最终会出现在python中,但这更像是一个普遍的问题.

蛮力太慢了.我需要一个近词典速度查找.有人有想法吗？

Answer 1

我建议实现一个kd-tree,你可以在其上执行最近邻搜索.k维中N个点的最坏情况搜索时间是O(k.N^(1-1/k))如此,它应该在N中线性地缩放.

如果我有时间,我会回到这个答案并提供维基百科的简洁解释.

由于你在python中工作,这个关于kdtrees的 Scipy食谱条目 应该有所帮助.

Answer 2

另一种被证明有用的技术是局部敏感哈希： http://en.wikipedia.org/wiki/Locality_sensitive_hashing

从您的问题中尚不清楚您是否需要“精确的”最近邻居。如果您对返回近似最近邻的向量感到满意，那么还有更快的解决方案。请参阅此处（http://www.cs.umd.edu/~mount/ANN/）