c++ - 分割大量的3D点数据

Question

我需要对一大组 3D 点进行分区(使用 C++)。点以二进制 float 组的形式存储在硬盘上，文件通常大于10GB。我需要将该集合划分为大小小于 1GB 的较小子集。子集中的点应该仍然具有相同的邻域，因为我需要对数据执行某些算法(例如，对象检测)。

我想我可以使用 KD-Tree。但是，如果不能将所有点都加载到 RAM 中，我如何有效地构建 KD 树呢？也许我可以将文件映射为虚拟内存。然后我可以保存一个指向属于一个段的每个 3D 点的指针，并将其存储在 KD 树的一个节点中。那行得通吗？还有其他想法吗？

感谢您的帮助。我希望你能理解这个问题:D

Answer 1

您基本上需要一个核外算法来计算(近似)中位数。给定一个大文件，找到它的中位数，然后将它分成两个较小的文件。 k-d 树是沿不同维度递归应用此过程的结果(当较小的文件开始适合内存时，您不必再为核外算法烦恼)。

要估计大文件的中位数，请使用 reservoir sampling获取大量但内存中的样本，然后运行核心中值查找算法。或者，对于精确的中位数，计算(例如)大约第 45 和第 55 个百分位数，然后进行另一遍以提取它们之间的数据点并准确计算中位数(除非样本异常非随机，在这种情况下重试)。有关详细信息，请参阅 Motwani--Raghavan 关于随机算法的书。