Point Cloud Indexing Using Big Data Technologies

We present a system for scalable indexing of very large point cloud data in the cloud using common Big Data technologies. We adjusted the procedure for building the common modifiable-nested-octree data-structure to the Map-Reduce paradigm using Morton-Codes for fast point grouping and sampling. Our system requires only two shuffle operations independently of the size of the point cloud, thus enabling linear scalability with the number of cluster nodes. Combining the modifiable-nested-octree with a hash-based grid also allows our system to efficiently deal with data updates. Based on a series of experiments with freely available point cloud datasets of up to 82 billion points we show that our system outperforms the state-of-the-art by up to a factor of 3. As our system is cloud-native, even the largest point cloud datasets can be indexed efficiently. Storing the resulting data-structure in a distributed database enables fast range queries supporting level of detail for web-based rendering.