划分大量的3D点数据

Question

我需要分割一大堆3D点(使用C++).这些点作为二进制浮点数组存储在HDD上,文件通常大于10GB.我需要将集合划分为大小小于1GB的较小子集.子集中的点应该仍然具有相同的邻域,因为我需要对数据执行某些算法(例如,对象检测).

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

谢谢您的帮助.我希望你能解决这个问题:D

Answer 1

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

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