允許插入的高效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中找到。