问题陈述：
在三维空间中有超过十亿个点。目标是找到距离小于给定距离 R 的最多邻居点数的前 N 个点。另一个条件是这些前 N 个点之间的距离必须大于 R。这些点的分布不均匀，很常见某些区域包含了大量的点。
目标：
找到一种算法，该算法能够适应许多处理器并且内存需求小。
想法：
由于分布不均匀，通常的空间分解对于这种问题来说是不足够的。采用不规则的空间分解可以将点的数量均匀地分配，从而有助于解决该问题。如果有人能够为我们提供一些解决方案，我将非常感激。
3D聚类算法
10
- Teng Lin
2
1这听起来像是集合覆盖问题的三维变体！！ :-) - Jérémie
你的问题让我想起了“矢量量化”，这个网站可能会给你一些启示：http://www.data-compression.com/vq.shtml。乍一看，如果你去掉这个限制：“这N个顶点中任意两点之间的距离必须大于R”，那么这个问题应该不难解决——这个限制导致了很大的问题，需要很多思考才能解决。 - SigTerm
5个回答
4
使用八叉树。对于数值域有限且可扩展到大数据集的3D数据非常有效。
许多上述方法，如局部敏感哈希，是设计用于更高维度的近似版本，其中无法再合理地分割。
在每个级别将其分成8个箱子（d=3时为2^d）非常有效。由于可以在单元格中的点过少时停止，并在有很多点的地方建立更深的树，这应该很好地满足您的要求。
有关更多详细信息，请参见维基百科：
许多上述方法，如局部敏感哈希，是设计用于更高维度的近似版本，其中无法再合理地分割。
在每个级别将其分成8个箱子（d=3时为2^d）非常有效。由于可以在单元格中的点过少时停止，并在有很多点的地方建立更深的树，这应该很好地满足您的要求。
有关更多详细信息，请参见维基百科：
https://en.wikipedia.org/wiki/Octree
另外，您可以尝试构建R树。但是，R树会尝试平衡，使得查找最密集区域更加困难。对于您的特定任务，Octree的这个缺点实际上很有帮助！ R树花费了很多精力来保持树的深度均匀，以便每个点可以在大致相同的时间内找到。然而，您只对密集区域感兴趣，这些区域将在Octree中最长的路径上找到，甚至不必查看实际点！
- Has QUIT--Anony-Mousse
2
以下是可能的解决方案的一些部分。
每个阶段都有各种选择，
这将取决于Ncluster，数据变化的速度以及您想要对平均值进行什么操作。
3个步骤：量化、盒子、K-均值。
1）量化：通过单独取X、Y、Z的2^8百分位数，将输入XYZ坐标降低到每个坐标使用8位， 这样可以加速整个流程而不会损失太多细节。 您可以对所有1G点进行排序，也可以随机选择1M个点， 以获得8位x0添加：Kd树 将任何点云分割成不同大小的盒子，每个盒子含有约Leafsize个点—— 比上面的X Y Z分割要好得多。 但是据我所知，您需要编写自己的Kd树代码， 仅拆分前16M个盒子，并仅保留计数，而不是点。 2）盒子：计算每个3D盒子中的点数， [xj..xj+1，yj..yj+1，zj..zj+1]。 平均每个盒子将具有2^(30-3*8)个点; 分布将取决于数据的聚集程度。 如果某些盒子太大或包含太多点，则可以 a）将它们分成8个， b）跟踪每个盒子中的点的中心， 否则只需采用盒子中点的中点。
3个步骤：量化、盒子、K-均值。
1）量化：通过单独取X、Y、Z的2^8百分位数，将输入XYZ坐标降低到每个坐标使用8位， 这样可以加速整个流程而不会损失太多细节。 您可以对所有1G点进行排序，也可以随机选择1M个点， 以获得8位x0添加：Kd树 将任何点云分割成不同大小的盒子，每个盒子含有约Leafsize个点—— 比上面的X Y Z分割要好得多。 但是据我所知，您需要编写自己的Kd树代码， 仅拆分前16M个盒子，并仅保留计数，而不是点。 2）盒子：计算每个3D盒子中的点数， [xj..xj+1，yj..yj+1，zj..zj+1]。 平均每个盒子将具有2^(30-3*8)个点; 分布将取决于数据的聚集程度。 如果某些盒子太大或包含太多点，则可以 a）将它们分成8个， b）跟踪每个盒子中的点的中心， 否则只需采用盒子中点的中点。
3) 在2^(3*8)个盒子中心上进行K-means聚类。(谷歌并行"k means"-> 121k hits。) 这在很大程度上取决于K，也就是Ncluster，以及你的半径R。一个粗略的方法是使用最多点的27 * Ncluster个盒子构建一个堆，然后根据你的半径约束选择最大的盒子。(我喜欢从最小生成树开始, 然后删除最长的K-1条链接来得到K个簇。) 参见颜色量化。
我会从一开始就将Nbit（这里为8）作为参数。
你的Ncluster是多少？
补充：如果你的点随时间移动，请参考SO上的大量圆形的碰撞检测。
- denis
2
我没有一个明确的答案给你，但我有一个建议，可能会产生一个解决方案。
我认为值得研究一下局部敏感哈希。将点均匀分割，然后对每个集合应用这种类型的LSH似乎是可以很容易地并行化的。如果您设计哈希算法，使桶大小以
在本地执行此操作后，您可以应用某种类似于Map-Reduce的策略，以逐步合并来自LSH算法不同并行运行的空间桶，利用您可以通过折扣整个桶来开始排除问题空间部分的事实。显然，您必须小心处理跨越不同桶的边缘情况，但我认为在每个合并阶段，您可以应用不同的桶大小/偏移量，以消除这种效应（例如，在空间上执行相当的桶合并，以及相邻的桶）。我相信这种方法可以使内存需求保持较小（即，您任何时候都不需要存储比点本身更多的内容，并且您始终在处理较小的子集）。
如果您正在寻找某种启发式方法，那么我认为此结果将立即产生类似于“良好”解决方案的东西 - 即它将给出一小部分可能的点，您可以检查它们是否满足您的标准。如果您正在寻找确切答案，则必须在开始合并并行桶时应用其他方法来修剪搜索空间。
另一个我想到的想法是这可能与寻找度量空间 k-中心有关。虽然绝对不是完全相同的问题，但解决该问题所使用的某些方法可能适用于此案例。问题在于，这假定您有一个度量空间，可以计算距离度量 - 然而，在您的情况下，十亿个点的存在使得执行任何全局遍历（例如对点之间的距离进行排序）变得不可取和困难。正如我所说，这只是一个想法，或许可以激发进一步的灵感。
我认为值得研究一下局部敏感哈希。将点均匀分割，然后对每个集合应用这种类型的LSH似乎是可以很容易地并行化的。如果您设计哈希算法，使桶大小以
R为定义，那么对于给定的点集分成的桶，满足您条件的点很可能存在于最满的桶中。在本地执行此操作后，您可以应用某种类似于Map-Reduce的策略，以逐步合并来自LSH算法不同并行运行的空间桶，利用您可以通过折扣整个桶来开始排除问题空间部分的事实。显然，您必须小心处理跨越不同桶的边缘情况，但我认为在每个合并阶段，您可以应用不同的桶大小/偏移量，以消除这种效应（例如，在空间上执行相当的桶合并，以及相邻的桶）。我相信这种方法可以使内存需求保持较小（即，您任何时候都不需要存储比点本身更多的内容，并且您始终在处理较小的子集）。
如果您正在寻找某种启发式方法，那么我认为此结果将立即产生类似于“良好”解决方案的东西 - 即它将给出一小部分可能的点，您可以检查它们是否满足您的标准。如果您正在寻找确切答案，则必须在开始合并并行桶时应用其他方法来修剪搜索空间。
另一个我想到的想法是这可能与寻找度量空间 k-中心有关。虽然绝对不是完全相同的问题，但解决该问题所使用的某些方法可能适用于此案例。问题在于，这假定您有一个度量空间，可以计算距离度量 - 然而，在您的情况下，十亿个点的存在使得执行任何全局遍历（例如对点之间的距离进行排序）变得不可取和困难。正如我所说，这只是一个想法，或许可以激发进一步的灵感。
- Gian
5
这确实非常类似于最大覆盖问题。目标函数不同。这里的目标是将Sum((Ci-Ct/K)^2)最小化，其中i = 1,..K，K是分区数，Ci是集合i中点的数量，Ct是总点数。 - Teng Lin
Ci并不是我们想要优化的变量，但它应该足够接近。理想情况下，Ci还应包括其表面邻近单元格中点数的数量。由于单元格大小为R，因此距离计算只需要扩展其最近邻的单元格即可。 - Teng Lin
我现在想到的一个想法是创建LxMxN个单元格（每个单元格的长度为R）。可以轻松记录每个单元格中的点数。然后可以使用聚类算法来查找密集的簇。由于点的数量太多，对于每个点执行聚类算法是不可行的。但是，我们可以通过将LxMxN单元格中的计数除以任意数字来降低分辨率。例如，Ct /（LMN）。然后可以利用贪心算法进行划分。不确定是否正确。 - Teng Lin
我不太确定前两个评论是关于什么的。然而，你描述的最后一种方法基本上就是我所建议的——某种空间分割（例如LSH），它允许你在桶中计算点数以定位可能的解决方案，然后你可以检查它们（此外，如果你的桶大小是以R为单位的，那么你实际上可以开始对当前桶和相邻桶中的点进行正常的距离度量）。 - Gian
前两个注释与将数据放入网格后的数据分区相关。 - Teng Lin
0
一个想法。根据给定的点和距离小于R的边创建图。
这种图的创建类似于空间分解。您的问题可以通过图中的本地搜索来回答。首先是具有最大度数的顶点，其次是查找最大不相连的最大度数顶点集。
我认为可以并行创建图形和搜索。这种方法可能需要大量的内存。拆分域并使用较小体积的图可以减少内存需求。
- Ante
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接