Paratreet: Parallel Software for Spatial Trees in Simulation and Analysis

Many applications involve organizing objects in hierarchical trees. These include astronomical simulations of particles moving under the influence of gravity, complex analytics of spatial data, photorealistic rendering of virtual environments, surface reconstruction from LIDAR, and collision detection for physical simulation. This project will develop a parallel tree toolkit and associated applications that will allow scientists to effectively utilize small clusters as well as very large supercomputers for parallel tree-based calculations. We plan to support a variety of spatial decomposition methods and the associated trees, including oct-trees, kd-trees, inside-outside trees, ball trees, R-trees, and their combinations. The framework will also include support for clusters of accelerators, such as GPGPUs.