c++ - 在 C 中处理非常大的距离矩阵(或 C++，如果有帮助的话)

Question

我正在实现这个聚类算法 http://www.sciencemag.org/content/344/6191/1492.full ( free access version ) 在我的软件中的 C 中，我需要构建一个距离矩阵，但在某些情况下，数据集的大小(冗余去除后)很大(n > 1 500 000，甚至更大，上升在更复杂的情况下增加到 4 000 000)。我的问题是，即使分配上三角矩阵也是 ( (1500000*1500000) - 1500000) * 0.5 * sizeof(float) =~ 5.5e12 Bytes。因此，内存分配失败(即使在我们具有 256 GB RAM 的计算节点上)并且在这种情况下写入磁盘不是一种选择。

除了减少要聚类的数据集的大小(我将查看)之外，有人知道我可以用来近似和存储这些信息量的技术吗？

注意正如我在标题中所说，我正在使用 C，也可以使用 C++。另外，如果有人要使用另一种聚类算法(其中聚类的数量由算法本身确定)，请向我推荐。

提前感谢您的宝贵时间，

Answer 1

您可能不得不退后一步，重新考虑您的算法。

首先，也许您不需要所有数据点对之间的距离矩阵。或许您可以将相似的数据点组合到数据箱中，然后创建箱之间的距离矩阵。

也就是说，首先计算点之间的成对距离，但只保留相对较小的距离和指向“另一个”点的指针。一种距离较短的非常稀疏的矩阵。这很容易并行执行。

然后创建数据箱，其中包含相互之间距离较小的点组。例如，如果您以这样的方式对“短”距离进行阈值处理，使垃圾箱平均保持 50 个数据点，您将获得 1500000/50=30000 个垃圾箱。

然后再次检查您的数据并计算 bin 之间的距离。这将产生 30000^2 个距离，这是一个大约 4GB 的矩阵。此外，您还有 30000 个，在 bin 内有 50^2 个距离，这又是 300MB。这种数据量非常易于管理。

如果将数据点之间的距离替换为相应 bin 之间的距离对于您的应用程序来说足够精确，那么它就可以工作。这完全取决于您处理的数据类型和应用程序的精度要求。