快速查找字典向量到給定的向量。高維

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條目應該有所幫助。