Balance Refinement of Massive Linear Octree Datasets

Many applications that use octrees require that the octree decomposition be smooth throughout the domain with no sharp change in size between spatially adjacent octants, thus impose a so-called 2-to-1 constraint on the octree datasets. The process of enforcing the 2-to-1 constraint on an existing octree dataset is called balance refinement. Although it is relatively easy to conduct balance refinement on memory-resident octree datasets, it represents a major challenge when massive linear octree datasets are involved. Different from other massive data problems, the balance refinement problem is characterized not only by the sheer volume of data, but also by the intricacy of the 2-to-1 constraint. Our solution consists of two major algorithms: balance by parts and prioritized ripple propagation. The key idea is to bulk load most of the data into memory only once and enforce the 2-to-1 constraint locally using sophisticated data structure built on the fly. The software package we developed has successfully balanced world-record linear octree datasets that are used by real-world supercomputing applications.