可更新的最近邻搜索

Question

我正在设计一个最近邻搜索应用程序，类似于这个问题：Saving and incrementally updating nearest-neighbor model in R。我的情况是在Python中实现，但主要问题是当有新数据时，必须更新模型/索引。我目前正在尝试使用scikit-learn neighbors module，但我不确定它是否适合。

应用程序的目标是：用户输入查询，然后显示现有数据集中n（可能会固定为5）个最近邻居。对于此步骤，来自sklearn的此类搜索结构将有所帮助，但在添加新记录时需要重新生成。此外，这是每次查询发生的第一步，因此可能会有些“慢”，比如2-3秒，而不是“立即”。

然后，用户可以单击其中一条记录并查看该记录的最近邻居等。这意味着我们现在在现有数据集内，并且NN可以预先计算并存储在redis中（现在有200k条记录，但可以扩展到数千万或数亿条记录）。这应该非常快速地浏览。

但是，在没有必要完全重新计算距离矩阵的情况下，如何更新预计算数据是一个问题，特别是因为新记录很少（每周大约100条）。

是否存在可更新的NN搜索工具、方法或算法？

- beginner_

---

由于您的“新”数据仅占“基础”数据的一小部分，因此最简单（并且在可预见的未来最有效）的方法是拥有两个最近邻数据结构，一个用于“基础”，另一个用于“新”，并使用一个适配器来隐藏拥有2个数据结构的复杂性。在适配器内部，您可以查询这两个结构以获取5个最近邻，然后进行暴力距离计算，以找出哪些是您实际的最近邻。 - Paul Brodersen

至少对于KD树，你遇到的基本问题是，虽然向现有树添加节点很容易（而且快速），但随着时间的推移，这会导致一棵不平衡的树，查找性能更差。由于从头开始构建树相当快（大约是O（n log n）），因此流行的实现（例如scipy.spatial中的KDtree）不支持在初始构建之后添加节点（在某个时候，sklearn中的实现只是scipy中的包装器，不确定现在是否仍然是这种情况）。 - Paul Brodersen

@Paul，是的，在KD树中重新平衡可能会成为一个问题，但只要新数据相当均匀分布或插入速率较慢，树就不应该明显失衡。然而，另一种选择是每1000次插入左右重新创建树，有些实现甚至有“重新平衡”操作。另一种选择是使用另一种树，如R*Tree（R星树）或简单的四叉树/八叉树/...（在5或6个维度上非常快）。 - TilmannZ

据我所了解，Balltrees只是一种加载标准树（如KD-tree）以更适合kNN查询的方法。这通常是通过批量加载（非增量加载）实现的，因此我不确定是否有增量方式。在此有两点需要注意：a）经过简短的互联网搜索，看起来BallTrees与nomal KD-Trees相比仅略快一些。b）RTree已经将点按接近程度分组，类似于BallTree，因此使用RTree可以免费获得类似BallTree的分组。 - TilmannZ

@TilmannZ 我实际上是通过谷歌搜索并找到了这个软件包，以下是2013年的一些性能统计数据和博客文章。https://jakevdp.github.io/blog/2013/04/29/benchmarking-nearest-neighbor-searches-in-python/ - beginner_

Answer 1

你可以尝试使用Milvus，它支持向量的添加和近实时搜索。

这里是Milvus的基准测试结果。

- Lea

Answer 2

您应该研究FAISS及其IVFPQ方法。您可以为每个更新创建多个索引，并将它们与旧索引合并。

- jokol

---

IVFPQ支持增量索引，因此不需要多个索引。 - Matthijs Douze

Answer 3

nmslib 支持添加新向量。它被 OpenSearch 用作相似性搜索引擎的一部分，而且速度非常快。

但有一个注意点：

虽然 HNSW 算法允许增量添加点，但禁止删除和修改索引点。

您也可以考虑像Milvus或Vearch这样的解决方案。

- Eric L