最近邻3D w/ Delete & Add操作

Question

是否存在支持删除和添加操作以及精确的最近邻查询的最近邻数据结构？在理想情况下寻找Python实现。

尝试：

• 在高维空间中找到了许多近似最近邻查询的实现。
• 找到KD树和球状树，但它们不允许动态平衡。
• 认为局部敏感散列算法是可能的。
• 看着OctTrees。

上下文：

1. 对于10,000个点的每一点，查询其最近的邻居
2. 评估每对邻居
3. 选择一个点并删除这对点，并添加一个合并点。
4. 重复某些次数的迭代

Answer 1

是。存在这样一种数据结构。我发明了一个。我手头正好有这个问题。这种数据结构使得KD树显得过于复杂。它只包含点在每个维度中的排序列表。

显然，您可以从n个列表中添加和删除一个n维点，按照它们各自的维度排序，而不存在任何问题。很多技巧都允许一个人迭代这些列表，并在数学上证明你有一个点的最短距离。有关精化和代码，请参见我的答案here。

不过，我必须指出，你的背景是错误的。A的最近点可能是B，但它并不认为B的最近点一定是A，你可以构造一个点链，使得每个环节之间的每一段距离都小于以前的距离，但也必然比其他点更远，因此只有一对邻居共享它们最近的邻居。