嵌入向量搜索高效算法。

Question

背景：我有一个机器学习模型，给定一个对象会返回一个维度为d的嵌入向量，该模型是按照语义相似性训练的，使得两个嵌入向量的语义相似性非常接近。现在，验证过程相对简单，我可以像比较两个向量的余弦相似度这样做。对于识别来说，稍微有点复杂，我可以循环遍历所有锚点文档并比较余弦相似度，或者使用类似kNN(在线)的方法。

问题：我有一个嵌入向量列表，每个向量都具有长度为N的维度d的浮点数据。

什么样的高效的数据结构和算法能够实现以下操作：

1. 能够高效地（<= 对数复杂度）向列表中添加一个带有唯一ID的新向量
2. 能够高效地（希望是<= 对数复杂度）搜索列表中的任意向量，并检索出与它们曼哈顿距离/L1范数最小的前k个向量。

例子：

[
 [1., 2., 3.],
 [5., 6., 8.],
 [-11., 2., 31.]
]

k = 2 查询 = [1.5、2.5、3.2] 结果：

[
 [1., 2., 3.],
 [5., 6., 8.],
]

- Zabir Al Nazi

---

我会研究近似最近邻算法。根据数据（特别是N>> d的情况），采用某种形式的局部敏感哈希或基于kd-tree的方法似乎是适当的选择。 - tzaman

谢谢，这确实很有帮助。我在这里找到了一些好的资源：https://www.infoworld.com/article/3634357/what-is-vector-search-better-search-through-ai.html - Zabir Al Nazi

我写了一些关于ANN算法的文章，你可能会发现它们很有用。你可以采用各种方法，比如IVF或HNSW，也可以混合匹配几种组合。对你的问题的答案取决于数据集的大小，而不是其他任何因素，特别是对于特别大的数据集（1M+），最好使用IVF+HNSW。 - James Briggs

谢谢，@JamesBriggs。我会研究一下的。 - Zabir Al Nazi

是的，向量的数量将达到1M+。 - Zabir Al Nazi

Answer 1

我认为Faiss正是你需要的。如果你对实现细节感兴趣（这相当技术性），请查看这里，Github页面在这里，教程在这里。

- Phoenix

Answer 2

随着神经网络被广泛应用于许多不同的软件产品中，这个问题变得非常普遍，因此有许多算法可供选择。

选择适合您问题的正确工具将基于以下权衡：

• 速度：您希望算法/库有多快？
• 召回率：检索到的嵌入是最佳邻居的频率。

这些权衡在http://ann-benchmarks.com/中以不同的包为基础进行了很好的展示，该网站对许多不同的近似最近邻算法搜索包进行了基准测试。这将是一个很好的起点。

从长期可维护性的角度考虑，您还需要考虑社区（例如git存储库星标，最新推送，PR），代码质量等因素。

- abhiieor