8

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

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

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

思考: 由于分布不均匀,正态空间分解不足以解决这类问题。将点数均分的不规则空间分解可能有助于我们解决问题。如果有人能阐明如何解决这个问题,我将不胜感激。

4

5 回答 5

4

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

许多上述方法(例如局部敏感散列)是为更高维度设计的近似版本,您无法再进行明智的拆分。

将每个级别拆分为 8 个箱(d=3 时为 2^d)效果很好。而且由于您可以在单元格中的点太少时停止,并构建一个更深的树,其中有很多点应该非常适合您的要求。

有关更多详细信息,请参阅维基百科:

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

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

于 2012-09-04T06:21:54.443 回答
2

我没有给你一个明确的答案,但我有一个可能产生解决方案的方法的建议。

我认为值得研究locality-sensitive hashing。我认为将这些点平均分配,然后将这种 LSH 应用于每组应该很容易并行化。如果您设计散列算法以使存储桶大小R

在本地执行此操作后,也许您可​​以应用某种 map-reduce 风格的策略,以逐步方式组合来自 LSH 算法的不同并行运行的空间桶,利用您可以开始排除部分通过折扣整个存储桶来解决您的问题空间。显然,您必须小心跨越不同存储桶的边缘情况,但我怀疑在合并的每个阶段,您可以应用不同的存储桶大小/偏移量,以便消除这种影响(例如,执行合并空间等效存储桶,以及作为相邻的桶)。我相信这种方法可用于保持较小的内存需求(即,在任何给定时刻,您不应该需要存储比点本身更多的东西,并且您总是在小(ish)子集上进行操作)。

如果您正在寻找某种启发式方法,那么我认为这个结果将立即产生类似于“好”解决方案的东西 - 即它将为您提供少量可能的点,您可以检查这些点是否满足您的标准。如果您正在寻找一个确切的答案,那么当您开始合并并行存储桶时,您将不得不应用一些其他方法来修剪搜索空间。

我的另一个想法是,这可能与找到度量k -center有关。这绝对不是完全相同的问题,但也许解决时使用的一些方法适用于这种情况。问题是,这假设您有一个度量空间,可以在其中计算距离度量 - 但是,在您的情况下,十亿个点的存在使得执行任何类型的全局遍历(例如距离排序)变得不可取且困难点之间)。正如我所说,只是一个想法,也许是进一步灵感的来源。

于 2010-08-14T22:41:00.197 回答
1

我还建议使用八叉树。OctoMap框架非常擅长处理巨大的 3D 点云。它不直接存储所有点,而是更新每个节点的占用密度(也称为 3D 框)。树构建完成后,您可以使用简单的迭代器来查找密度最高的节点。如果您想对节点内的点密度或分布进行建模,OctoMap 很容易采用。

在这里,您可以看到它是如何扩展为使用平面模型对点分布进行建模的。

于 2013-09-04T16:02:35.760 回答
1

以下是解决方案的一些可能部分。每个阶段都有不同的选择,这取决于 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 上的大规模圆数碰撞检测。

于 2010-09-06T10:38:46.683 回答
0

只是一个想法。当距离 < R 时,创建具有给定点和点之间边的图形。

这种图的创建类似于空间分解。您的问题可以通过图表中的本地搜索来回答。首先是具有最大度数的顶点,其次是找到最大度数顶点的最大未连接集。

我认为图形和搜索的创建可以并行进行。这种方法可能需要大量内存。拆分域并使用图形处理较小的卷可以减少内存需求。

于 2011-07-29T11:22:39.300 回答