问题陈述： 我有以下问题：
3D 空间中有超过十亿个点。目标是在给定距离R内找到具有最多邻居数的前N个点。另一个条件是这些前N个点的任意两点之间的距离必须大于R。这些点的分布不均匀。空间的某些区域包含很多点是很常见的。
目标： 找到一种可以很好地扩展到许多处理器并且内存需求很小的算法。
思考： 由于分布不均匀，正态空间分解不足以解决这类问题。将点数均分的不规则空间分解可能有助于我们解决问题。如果有人能阐明如何解决这个问题，我将不胜感激。
问问题
9764 次
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
以下是解决方案的一些可能部分。每个阶段都有不同的选择，这取决于 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 回答