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

Question

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

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

一些想法：

这里有什么好的选择？

Answer 1

我同意（几乎）@gsamaras 所说的一切，只是添加一些内容：

根据我的经验（使用大于等于 500,000 点的大型数据集），KD 树的 kNN 性能比几乎任何其他空间索引差 10 到 100 倍。我测试了它们（2 个 KD 树和各种其他索引））在大型 OpenStreetMap 数据集上。在下图中，KD-Tree 称为 KDL 和 KDS，2D 数据集称为 OSM-P（左图）：该图取自本文档，有关更多信息，请参阅下面的要点。
这项研究描述了一种用于移动对象的索引方法，以防您在略有不同的位置不断（重新）插入相同的点。
四叉树也不错，它们在 2D 中速度非常快，对于少于 1,000,000 个条目的数据集具有出色的 kNN 性能。
如果您正在寻找 Java 实现，请查看我的索引库。有四叉树、R 星树、ph 树等的实现，所有这些都具有也支持 kNN 的通用 API。该库是为TinSpin编写的，TinSpin 是一个用于测试多维索引的框架。可以找到一些结果，在此处输入链接描述（它并没有真正描述测试数据，但“OSM-P”结果基于具有多达 50,000,000 个 2D 点的 OpenStreetMap 数据。
根据您的情况，您可能还需要考虑PH-Trees。对于 kNN 查询，它们在低维度上似乎比 R树慢（尽管仍然比 KD 树快），但它们的删除和更新速度比 R 树更快。如果您需要进行大量移除/插入，这可能是更好的选择（参见TinSpin 结果，图 2 和 46）。（我的）C++ 版本可以在这里找到。

Answer 2

检查Bkd-Tree，它是：

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

然而，这种数据结构是多维的，并且不专门用于较低维度（如 kd 树）。

在bkdtree中使用它。

动态四叉树也可以是候选者，具有 O(logn) 查询时间和 O(Q(n)) 插入/删除时间，其中 Q(n) 是在所使用的数据结构中执行查询的时间。请注意，此数据结构专门用于 2D。然而，对于 3D，我们有八叉树，并且以类似的方式可以将结构推广到更高的维度。

一个实现是QuadTree。

R*-tree是另一种选择，但我同意你的普遍性。r -star-tree实现也存在。

也可以考虑覆盖树，但我不确定它是否符合您的描述。在这里阅读更多内容，并检查CoverTree上的实现。

Kd 树仍然应该被考虑，因为它在二维上的性能非常出色，并且它的插入复杂度是对数的。

nanoflann和CGAL只是它的两个实现，第一个不需要安装，第二个不需要安装，但性能可能更高。

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