algorithm - 找到最近的向量

Question

我们有一个维度大于 2（维度可以是 10、32、64 或 15）的向量列表和一个任意向量作为输入。

需要从向量列表中找到最接近输入向量的

（例如：10000 和 10001 是近向量，但 10111 和 10000 不是近向量），但没有完整通过列表。我知道几种最近邻搜索算法，它们可以让我们找到最接近的相似元素：kd-trees、Voronoi 图，但它们的目的是在平面或 3 维空间中查找元素。

是否有任何算法可以找到最近的向量，哪个维度大于 2？

标签： algorithmsearch

Answer 1

几乎所有最近邻搜索的索引结构都支持多维数据。

例如， KD-Trees和R-Trees非常适合低维数据（d < 5-10）。当维度数量增加时，您会遇到维度灾难，并且大多数索引结构都会退化（它们变得不那么有选择性）。

除了 20 维（这只是一个经验法则并且高度依赖于数据分布）之外，这些传统的索引结构与对数据的全面扫描相比没有任何好处。然后你可以

• 尝试优化此扫描（例如，在距离计算或VA-File期间提前停止）
• 使用快速但不保证返回最近邻（但通常是近邻）的近似最近邻方法（例如，局部敏感散列法）