带动态点的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。