嵌入向量搜索高效算法

Question

背景： 我有一个机器学习模型，其中给定一个对象 returns 一个维度为 d 的嵌入向量，该模型的训练方式使得两个嵌入向量的语义相似度非常接近。现在，验证过程相对简单，我可以取两个向量的余弦相似度之类的东西。对于识别，它有点复杂，我可以循环遍历所有锚文档并比较余弦相似度，或者使用 kNN 之类的东西（在线）。

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

什么是高效的数据结构+算法，可以做到以下几点：

可以有效地将具有唯一 ID 的新向量添加到列表中（<= 对数复杂度）
使用列表中的随机向量进行搜索，并检索前 k 个向量，使得曼哈顿距离/L1 范数对于这些向量有效地最小（希望 <= 对数复杂度）。

示例：

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

k = 2 query = [1.5, 2.5, 3.2] results:

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

Answer 1

我认为 Faiss 正是您要找的人。 Github 页是 here, if you are interested in the implementation details (this is pretty technical) see here, and the tutorial is here。

Answer 2

随着许多不同软件产品中包含神经网络，这个问题变得非常普遍，因此有许多算法可以解决这个问题。

至 select 适合您问题的工具将基于

之间的权衡

speed：您希望 algo/library 多快？
recall：检索到的嵌入是最佳邻居的频率。

在 http://ann-benchmarks.com/ 中很好地体现了不同包的权衡，它对许多不同的近似最近邻算法搜索包进行了基准测试。这将是一个很好的起点。

从长期可维护性的角度来看，您还需要考虑社区（例如 git 回购明星、最新推送、PR）、代码质量等

嵌入向量搜索高效算法

embedding vector search efficient algorithm

python

algorithm

search

similarity

data-structures