algorithm - 3D聚类算法

Question

问题陈述:我有以下问题:

3D 空间中有超过 10 亿个点。目标是找到在给定距离 R 内具有最多邻居数的前 N ​​个点。另一个条件是前 N 个点中任意两点之间的距离必须大于 R。这些点的分布是不均匀的。空间的某些区域包含很多点是很常见的。

目标:寻找一种可以很好地扩展到许多处理器并且内存需求小的算法。

想法:由于分布不均匀，正常的空间分解不足以解决此类问题。均匀划分点数的不规则空间分解可能会帮助我们解决问题。如果有人能阐明如何解决这个问题，我将非常感激。

Answer 1

使用八叉树。对于具有有限值域的 3D 数据，可以很好地扩展到庞大的数据集。

上述许多方法(例如局部敏感哈希)都是为您无法再进行合理拆分的更高维度设计的近似版本。

将每个级别拆分为 8 个 bin(d=3 时为 2^d)效果很好。并且由于您可以在单元格中的点太少时停止，并在有很多点的地方构建一个更深的树，应该能很好地满足您的要求。

更多详细信息，请参阅维基百科:

https://en.wikipedia.org/wiki/Octree

或者，您可以尝试构建 R 树。但是 R-tree 试图平衡，这使得找到最密集的区域变得更加困难。对于您的特定任务，八叉树的这个缺点实际上很有帮助! R-tree 付出了很多努力来保持树的深度在每个地方都相等，因此每个点都可以在大约相同的时间找到。但是，您只对密集区域感兴趣，这些区域位于八叉树中最长的路径上，甚至无需查看实际点!