Trees are ubiquitous in Computer Science. They have applications in every aspect of computing from XML/HTML processing to abstract syntax trees (AST) in compilers, phylogenetic trees in computational genomics or shortest path trees in path planning. The ever increasing amounts of structured, hierarchical data processed in many applications have turned the processing of the corresponding large tree structures into a bottleneck, particularly when they do not fit in memory. Succinct tree representations store trees using as few bits as possible and thereby significantly increase the size of trees that fit in memory while still supporting important primitive operations in constant time. There exist such representations that use only bits to store the topology of a tree with n nodes, which is close to the information-theoretic lower bound and much less than the space used by traditional pointer-based representations.
The construction of succinct trees is quite slow compared to the construction of pointer-based representations. Multicore parallelism offers one possible tool to speed up the construction of succinct trees, but little work has been done in this direction so far. The only results we are aware of focus on the construction of Wavelet trees, which are used in representations of text indexes.
In this work, we provide a parallel algorithm that constructs the Range Min-Max Tree representation of  in time using cores. This structure uses bits to store an ordinal tree with n nodes and supports a rich set of basic operations on these trees in time. While this query time is theoretically suboptimal, the Range Min-Max Tree structure is simple enough to be practical and has been verified experimentally to be very small and support fast queries in practice . Combined with the fast parallel construction algorithm presented in this paper, it provides an excellent tool for manipulating very large trees in many applications. We implemented and tested our algorithm on a number of real-world input trees having billions of nodes. Our experiments show that our algorithm run on a single core is competitive with state-of-the-art sequential constructions of the Range Min-Max Tree structure and achieves good speed-up on up to cores and likely beyond.
An author's version of our work can be downloaded here. The link to the official version is here.
The code for this work is available at github.
This work was supported the doctoral scholarship of CONICYT (21120974) and in part by the Emerging Leaders in the Americas scholarship programme