三维聚类算法

Question

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

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

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

思想: 由于分布不均匀,正常的空间分解不足以解决这类问题.不均匀的空间分解,均匀分割​​点数可能有助于我们解决问题.我真的很感激,如果有人可以解释如何解决这个问题.

Answer 1

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

我认为值得研究局部敏感哈希。我认为均匀地划分这些点，然后将这种 LSH 应用于每个集合应该很容易并行。如果您设计哈希算法，使得存储桶大小根据 定义R，则对于划分为存储桶的给定点集，满足您的条件的点可能存在于最满的存储桶中。

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

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

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