algorithm - 如何找到稀疏向量的最近邻

Question

我有大约 500 个向量，每个向量是一个 1500 维的向量，几乎每个向量都非常稀疏——我的意思是只有大约 30-70 维的向量不为 0。

现在，问题是这里有一个给定的矢量，也是 1500 维，我需要将它与 500 个矢量进行比较，以找出这 500 个矢量中哪一个是最近的。(欧氏距离)。

毫无疑问，暴力法是一种解决方案，但我需要计算500次距离，这需要很长时间。

昨天看了一篇文章“Object retrieval with large vocabularies and fast spatial matching”，里面说使用倒排索引会有帮助，里面说:

但经过我的测试，这几乎没有任何意义，想象一个 1500 个向量，其中 50 个维度不为零，当涉及到另一个维度时，它们可能总是具有相同的维度而不是零。也就是说，这个算法只能排除很少的向量，我还需要和剩下的很多向量进行比较。

感谢您阅读到这里，我的问题是:

1.这个算法有意义吗？

2.有没有其他方法可以做我想做的事？比如法兰绒或 Kd-TREE？但我想要精确的最近邻，一个近似的是不够的

Answer 1

这种索引称为倒排列表，通常用于文本。

例如，Apache Lucene 使用这种索引进行文本相似性搜索。

本质上，您使用的是柱状布局，并且您只存储非零值。为了提高磁盘效率，可以采用各种压缩技术。

然后您可以使用这些列表上的集合操作来计算许多相似性。

这里不能使用k-d-trees。如果您有许多重复(零)值，它们将非常低效。