帶動態點的2D最近鄰居查詢算法

Question

我想找到一個快速算法來找到（近似的，如果需要的話）在二維空間中給定點的最近鄰居，其中點經常從數據集和新的點被添加。

（與此相關的，也有這個問題的兩個變種是引起我的興趣：一個在哪些點可以被看作是補充和隨機取出，另一種所有的點都在不斷地運動）

一些想法：

• KD樹提供了良好的性能，但只適用於靜態的點集
• R * - 樹似乎提供良好的性能，適用於各種尺寸，但其設計的通用性（任意尺寸，一般內容幾何）表明可能性，一個月再具體的算法可能會提供性能優勢
• 算法與現有的實現是優選的（雖然這不是必要的）

這裏有什麼好的選擇嗎？

Answer 1

檢查Bkd-Tree，其是：

一個I/O高效動態數據基於所述kd樹結構。 [...] Bkd-tree保持其較高的空間利用率，並且無論在其上執行更新的次數如何，其查詢和更新性能均爲。

然而，這種數據結構是多維的，並沒有專門針對較低的維度（如kd-tree）。

玩它在bkdtree。

---

Dynamic Quadtrees也可以是候選者，用O（logn）時間的查詢時間和O（Q（n））的插入/缺失時，其中Q（n）是在數據執行查詢的時間 結構使用。請注意，此數據結構專用於2D。然而，對於3D，我們有八叉樹，並且以相似的方式，可以將結構推廣到更高維度。

實施是QuadTree。

---

R*-tree是另一種選擇，但我同意你的一般性。 A r-star-tree也存在。

---

一個Cover tree可以考慮爲好，但我不知道它是否適合你的描述。閱讀更多here，並檢查CoverTree上的實施。

---

Kd-tree仍然應該考慮的，因爲它的性能是在2個維度顯着，其插入複雜的大小logarithic。

nanoflann和CGAL是它的兩個實現，其中第一個不需要安裝，第二個不需要安裝，但可能更高性能。

---

在任何情況下，我會嘗試多種方法和基準（因爲所有的人都實現，並且這些數據結構通常受數據的性質）。

Answer 2

我同意（幾乎）一切@gsamaras說，只是添加了一些東西：

• 根據我的經驗（使用大數據集> = 50萬個點），KD樹的KNN-性能比任何其他空間索引要差10到100倍。我在一個大的OpenStreetMap數據集上測試了它們（2個KD樹和各種其他索引）。在下圖中，KD-Trees被稱爲KDL和KDS，2D數據集被稱爲OSM-P（左圖）：該圖取自this document，有關詳細信息，請參閱下面的要點。
• This research描述了一種用於移動物體的索引方法，以防萬一您將相同的點保留（重新）插入稍微不同的位置。
• Quadtrees也不錯，它們可以在2D中非常快，對於數據集< 1,000,000個條目具有出色的kNN性能。
• 如果您正在尋找Java實現，請查看我的index library。 In中實現了四叉樹，R-star-tree，ph-tree等，它們都有一個也支持kNN的通用API。這個庫是爲TinSpin編寫的，這是一個測試多維索引的框架。一些結果可以發現enter link description here（它並沒有真正描述測試數據，但「OSM-P」的結果是基於與高達5000萬個2D點OpenStreetMap的數據。
• 根據您的情況，您可能還需要考慮PH-Trees，他們似乎是KNN-查詢比R * - 樹在低維較慢（不過仍低於KD樹更快），但它們對於拆除和更新除R更快*樹，如果你有很多去除/插入，這可能是一個更好的選擇（見TinSpin results，圖2和圖46）。A C++版本可用enter link description here。