允许插入的高效KNN实现

Question

假设我有多维数据集，其中有许多向量作为数据。我正在写一个算法，它需要做所有那些向量的k近邻搜索 - 经典KNN。然而，在我的算法中，我向整个数据集中添加了新的向量，并且需要将这些新的向量包含到我的KNN搜索中。我想要有效地做到这一点。我研究了scikit-learn的KD树和球树，但他们不允许插入（根据概念的性质）。我不确定SR树或R树是否会提供插入，但在任何情况下，我都无法找到3D以外的数据的Python实现。

关于搜索我很满意查询“给我最接近的向量”（所以1-NN）或“给我所有更接近半径的向量”。

Answer 1

一般评论：我不明白为什么KD树在高维kNN查询中非常流行。在我的experience中，其他树具有高维度或大数据集的规模要好得多（我测试了多达25百万个点和（仅）多达40个维度）。一些更多的细节：

• KD-Trees：据我所知，KD-Trees应该随时支持插入，但有可能它们不平衡。我不使用python，所以我不知道你的KD-tree为什么不支持动态插入/删除。四叉树：根据维度的不同，也可以使用四叉树/八叉树，但标准实现不适合超过10个维度左右。在上面的参考文献中，我用特殊的“hypecube”导航方法测试了一棵四叉树。这需要大量的内存，但在性能方面的维度更好。
• R-Tree/R *树：原始的R-Trees在动态插入时不太好。但是，如果您查看R +树（R-Plus-Tree），它们在重新插入和kNN查询方面速度非常快。
• PH-Trees具有与R +树基本相同的kNN性能，但插入时间要好得多，因为PH树不需要重新平衡，同时具有固有的深度和节点尺寸限制。不幸的是，对于大于等于64的维度，实现变得复杂得多（树对每个维度使用一个长整数的一位）。我不知道支持超过63个维度的实现。

的Python：

• R +优树应该为Python是可用的。如果没有，你可以适应一个普通的R-Tree（只有插入算法是不同的）
• 我听说有人开始在Python中实现一个PH-Tree，但我还没有看到任何开源变种。
• 如果您有时间/兴趣去做自己的实现，您可以查看Java实现here并将它们转换为Python。该库包含各种多维索引，但KD-Trees除外。允许实时插入的KD-Tree实现可以在here和here中找到。