python - 快速查找给定向量的字典向量。高维度

Question

我正在寻找可缩放的答案，但出于我的特定目的，我有一个 48 维向量。这可以表示为一个由 48 个整数组成的数组，这些整数都在 0 到 255 之间。

我有一本包含这些向量的大字典，大约有 25,000 个。

我需要能够获取可能存在或可能不存在于我的数据库中的向量，并快速找到数据库中最接近的向量。最近，我指的是传统距离公式。

我的代码将以 python 形式结束，但这是一个更普遍的问题。

蛮力太慢了。我需要一个接近字典的速度查找。有人有想法吗？

Answer 1

我建议实现 kd-tree您可以在其上执行 Nearest neighbour search . k 维中 N 个点的最坏情况搜索时间是 O(k.N^(1-1/k)) 因此它应该在 N 中呈次线性缩放。

如果我有时间，我会回到这个答案并提供一个不像维基百科那样简洁的解释。

因为你在 python 中工作，这个 Scipy 食谱条目在 kdtrees 上应该有帮助。