二维动态点最近邻查询算法

Question

我正在尝试找到一种快速算法，在一个二维空间中查找给定点的（近似）最近邻居，其中数据集中经常删除点并添加新点。

（相关地，我感兴趣的是这个问题的两个变体：一个是可以认为点是随机添加和删除的，另一个是所有点都在不断运动。）

一些想法：

- kd树提供良好的性能，但只适用于静态点集 - R * -trees似乎为各种维度提供了良好的性能，但其设计的普遍性（任意维度，通用内容几何）暗示着可能会有更具体的算法提供性能优势 - 最好使用现有实现的算法（尽管这不是必要的）

什么是一个好的选择？

- Richard

---

可能是https://stackoverflow.com/questions/45887680/efficient-knn-implementation-which-allows-inserts/45903853#45903853的重复问题。 - TilmannZ

Answer 1

我同意 @gsamaras 所说的（几乎）一切，只是想补充一些事情：

根据我的经验（使用大型数据集，点数≥500,000），KD-Tree的kNN性能比几乎任何其他空间索引差10到100倍。我在一个大型OpenStreetMap数据集上测试了它们（2个KD-Tree和其他各种索引）。在下面的图表中，KD-Tree被称为KDL和KDS，2D数据集被称为OSM-P（左图）： 这个图表来自于this document，更多信息请参考下面的要点。 这项研究描述了一种用于移动对象的索引方法，适用于将相同的点稍微不同位置进行（重新）插入的情况。

四叉树也不错，对于小于1,000,000条记录的2D数据集，它们可以非常快速，并且具有出色的kNN性能。

如果您正在寻找Java实现，请查看我的index library。它包含了四叉树、R-star-tree、ph-tree等的实现，所有这些实现都有一个共同的API，还支持kNN。该库是为TinSpin编写的，TinSpin是一个用于测试多维索引的框架。一些结果可以在enter link description here中找到（它并没有真正描述测试数据，但“OSM-P”结果是基于包含多达50,000,000个2D点的OpenStreetMap数据）。

根据您的情况，您可能还想考虑PH-Trees。在低维度上，它们的kNN查询速度似乎比R-Trees慢（尽管仍然比KD-Tree快），但是它们在删除和更新方面更快。如果您有大量的删除/插入操作，这可能是一个更好的选择（请参阅TinSpin results，图2和46）。C++版本可以在here找到（我的版本）。

- TilmannZ

Answer 2

检查一下Bkd-Tree，它是：

基于 kd-tree 的 I/O 有效的动态数据结构。[..] Bkd 树在不论执行多少次更新的情况下，都保持其高空间利用率和出色的查询和更新性能。

然而，该数据结构是多维的，与低维度（如 kd-tree）不专业化。

在bkdtree中试用一下。

---

“Dynamic Quadtrees”可以作为候选算法，其查询时间为O(logn)，插入/删除时间为O(Q(n))，其中Q(n)是所使用数据结构的查询时间。请注意，该数据结构专门用于二维。对于三维，我们有八叉树，并且以类似的方式可以将该结构推广到更高的维度。”

“QuadTree”的实现可以在这里找到。”

---

“R*-tree”是另一个选择，但我同意您所说的普适性。也存在r-star-tree的实现。”

---

一个Cover tree（覆盖树）也可以考虑，但我不确定它是否符合你的描述。更多信息请在这里阅读，并检查CoverTree（覆盖树）的实现。

---

“Kd-tree应该仍然被考虑，因为它在二维空间中的性能非常出色，而且插入复杂度随着大小的增加呈对数增长。”

“nanoflann和CGAL是它的两个实现，其中第一个不需要安装，第二个需要安装但可能更具性能。”

---

无论如何，我会尝试多种方法并进行基准测试（因为它们都有实现，并且这些数据结构通常受到你的数据性质的影响）。

- gsamaras

---

我对这些算法的问题在于它使用点，如果我存储具有实际尺寸的对象，则可能会重叠四叉树网格或KD树的分离线 - 没有一个例子能解释这种复杂性。 - WDUK

@WDUK：答案可能没有讨论那个问题，因为它不是我提出的问题的一部分。 - Richard

当然，但很多时候这些算法用于物理/粒子模拟优化，而且从来没有讨论过无限小点以外的情况，所以这些算法通常感觉未被探索，除了基本数据示例之外。因此，这些算法是否仍然有用超出基本点是不清楚的。@Richard - WDUK