问题陈述: 我有以下问题:
3D 空间中有超过十亿个点。目标是在给定距离R内找到具有最多邻居数的前N个点。另一个条件是这些前N个点的任意两点之间的距离必须大于R。这些点的分布不均匀。空间的某些区域包含很多点是很常见的。
目标: 找到一种可以很好地扩展到许多处理器并且内存需求很小的算法。
思考: 由于分布不均匀,正态空间分解不足以解决这类问题。将点数均分的不规则空间分解可能有助于我们解决问题。如果有人能阐明如何解决这个问题,我将不胜感激。
问题陈述: 我有以下问题:
3D 空间中有超过十亿个点。目标是在给定距离R内找到具有最多邻居数的前N个点。另一个条件是这些前N个点的任意两点之间的距离必须大于R。这些点的分布不均匀。空间的某些区域包含很多点是很常见的。
目标: 找到一种可以很好地扩展到许多处理器并且内存需求很小的算法。
思考: 由于分布不均匀,正态空间分解不足以解决这类问题。将点数均分的不规则空间分解可能有助于我们解决问题。如果有人能阐明如何解决这个问题,我将不胜感激。
使用八叉树。对于具有有限值域的 3D 数据,可以很好地扩展到大型数据集。
许多上述方法(例如局部敏感散列)是为更高维度设计的近似版本,您无法再进行明智的拆分。
将每个级别拆分为 8 个箱(d=3 时为 2^d)效果很好。而且由于您可以在单元格中的点太少时停止,并构建一个更深的树,其中有很多点应该非常适合您的要求。
有关更多详细信息,请参阅维基百科:
https://en.wikipedia.org/wiki/Octree
或者,您可以尝试构建 R 树。但是 R-tree 试图平衡,使得找到最密集的区域变得更加困难。对于您的特定任务,八叉树的这个缺点实际上很有帮助!R-tree 花了很多精力来保持树的深度在任何地方都相等,以便可以在大约同一时间找到每个点。但是,您只对密集区域感兴趣,这些区域可以在八叉树中最长的路径上找到,甚至无需查看实际点!
我没有给你一个明确的答案,但我有一个可能产生解决方案的方法的建议。
我认为值得研究locality-sensitive hashing。我认为将这些点平均分配,然后将这种 LSH 应用于每组应该很容易并行化。如果您设计散列算法以使存储桶大小R
以
在本地执行此操作后,也许您可以应用某种 map-reduce 风格的策略,以逐步方式组合来自 LSH 算法的不同并行运行的空间桶,利用您可以开始排除部分通过折扣整个存储桶来解决您的问题空间。显然,您必须小心跨越不同存储桶的边缘情况,但我怀疑在合并的每个阶段,您可以应用不同的存储桶大小/偏移量,以便消除这种影响(例如,执行合并空间等效存储桶,以及作为相邻的桶)。我相信这种方法可用于保持较小的内存需求(即,在任何给定时刻,您不应该需要存储比点本身更多的东西,并且您总是在小(ish)子集上进行操作)。
如果您正在寻找某种启发式方法,那么我认为这个结果将立即产生类似于“好”解决方案的东西 - 即它将为您提供少量可能的点,您可以检查这些点是否满足您的标准。如果您正在寻找一个确切的答案,那么当您开始合并并行存储桶时,您将不得不应用一些其他方法来修剪搜索空间。
我的另一个想法是,这可能与找到度量k -center有关。这绝对不是完全相同的问题,但也许解决时使用的一些方法适用于这种情况。问题是,这假设您有一个度量空间,可以在其中计算距离度量 - 但是,在您的情况下,十亿个点的存在使得执行任何类型的全局遍历(例如距离排序)变得不可取且困难点之间)。正如我所说,只是一个想法,也许是进一步灵感的来源。
以下是解决方案的一些可能部分。每个阶段都有不同的选择,这取决于 Ncluster、数据变化的速度以及你想用这些方法做什么。
3个步骤:量化,框,K-means。
1)量化:通过分别取 X、Y、Z 的 2^8 个百分位数,将输入的 XYZ 坐标减少到每个 8 位。这将加快整个流程,而不会丢失太多细节。您可以对所有 1G 点或随机 1M 点进行排序,以获得 8 位 x0 < x1 < ... x256, y0 < y1 < ... y256, z0 < z1 < ... z256 和 2^(30- 8) 每个范围内的点。要映射浮点 X -> 8 位 x,展开二分搜索很快 — 参见 Bentley,Pearls p。95.
补充:Kd 树 将任何点云分割成不同大小的盒子,每个盒子都有 ~ Leafsize 点——比上面分割 XYZ 好得多。但是 afaik 你必须滚动你自己的 Kd 树代码来分割第一个说 16M 的盒子,并且只保留计数,而不是分数。
2) box:统计每个3d box中的点数,[xj .. xj+1, yj .. yj+1, zj .. zj+1]。平均盒子会有 2^(30-3*8) 个点;分布将取决于数据的块状程度。如果某些框太大或得到太多点,您可以 a) 将它们分成 8 个,b) 跟踪每个框中点的中心,否则只取框的中点。
3) K-means 聚类 在 2^(3*8) 个盒子中心。(谷歌并行“k 表示”-> 121k 次点击。)这在很大程度上取决于 K aka Ncluster,也取决于您的半径 R。一种粗略的方法是增加 一堆 具有最多点的 27*Ncluster 框,然后取最大的受您的半径约束。(我喜欢从 最小生成树开始,然后删除 K-1 个最长的链接以获得 K 个簇。)另请参阅 颜色量化。
我会从一开始就将 Nbit,这里是 8 作为参数。
你的 Ncluster 是什么?
补充:如果您的点及时移动,请参阅 SO 上的大规模圆数碰撞检测。
只是一个想法。当距离 < R 时,创建具有给定点和点之间边的图形。
这种图的创建类似于空间分解。您的问题可以通过图表中的本地搜索来回答。首先是具有最大度数的顶点,其次是找到最大度数顶点的最大未连接集。
我认为图形和搜索的创建可以并行进行。这种方法可能需要大量内存。拆分域并使用图形处理较小的卷可以减少内存需求。