可更新的最近邻搜索

Question

我正在试着为最近邻居搜索应用程序想出一个好的设计。这与这个问题有些类似：

Saving and incrementally updating nearest-neighbor model in R

在我的例子中，这是在Python中实现的，但要点是当新数据到来时，模型/索引必须更新。我目前正在尝试使用scikit-learn neighbors module，但我不确定它是否适合它。

应用程序的目标是：

用户带着一个查询进来，然后将显示现有数据集中的n个(可能固定为5个)最近的邻居。对于这一步，来自sklearn的搜索结构会有所帮助，但在添加新的records.Also时必须重新生成。这是第一个ste，每次查询发生1次，因此可能会有点“慢”，因为与“即时”相比，在2-3秒内。

然后，用户可以单击其中一条记录，查看该记录最近的邻居，依此类推。这意味着我们现在在现有的数据集内，NN可以预先计算并存储在redis中(目前为200k条记录，但可以扩展到百万分之一或100万分之一)。这应该是非常快的浏览。

但在这里，我将面临同样的问题，即如何在不重新计算距离矩阵的情况下更新预计算数据，特别是因为几乎没有新记录(比如每周100个)。

是否存在这样的工具、方法或算法来进行可更新的NN搜索？

编辑4月3日：

正如许多地方所指出的那样，KDTree或BallTree并不真正适合高维数据。我已经意识到，对于一个只有200k条记录和512个维度的小数据集的概念验证来说，蛮力并不会太慢，大约是550ms对750ms。

然而，对于millions+中的大数据集，这个问题仍然没有解决。我看过数据草图LSH Forest，但在我的情况下，这似乎不够准确，或者我用错了它。将就此提出一个单独的问题。

Answer 1

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

Answer 2

您可以尝试Milvus，它支持矢量的添加和近乎实时的搜索。

这是米尔沃斯的benchmarks。

Answer 3

nmslib支持添加新的向量。它被Elasticsearch用作他们的Similarity Search Engine的一部分，它就是very fast。

需要注意的是：

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

您还可以研究像Milvus或Vearch这样的解决方案。