快速查找字典向量到给定的向量。高维

Question

我正在寻找一个缩放的答案，但对于我的具体目的，我有一个第48维向量。这可以表示为48个整数的数组，全部在0和255之间。

我有这些向量的大型字典，大约有25000个。

我需要能够采取可能或可能不在我的数据库中的矢量，并快速找到数据库中哪个矢量最接近。就最近而言，我的意思是用传统的距离公式。

我的代码将最终在Python中，但这是一个更普遍的问题。

蛮力太慢了。我需要近乎字典的速度查询。任何人有想法？

Answer 1

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

它不是从你的问题明确是否需要-exact-最近的邻居。如果您对返回近似最近邻的向量感到满意，则有更快的解决方案。看到这里（http://www.cs.umd.edu/~mount/ANN/）

Answer 2

我建议实施一个kd-tree，您可以在其中执行Nearest neighbour search。在k维中N个点的最坏情况搜索时间为O(k.N^(1-1/k))，所以它应该在N中以次线性比例缩小。

如果我有时间，我会回过头来回答这个问题，并提供维基百科的简短解释。

既然你在Python中工作，这个kdtrees上的Scipy Cookbook条目应该有所帮助。