Parallel Construction of Succinct Trees

Introduction

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 $2n+o<!--FUNCTION\; APPLICATION-->\left(n\right)$ 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 [1] in $O<!--FUNCTION\; APPLICATION-->(\frac{n}{\mathrm{p}}+\lg p)$ time using $\mathrm{p}$ cores. This structure uses $2n+o<!--FUNCTION\; APPLICATION-->\left(n\right)$ bits to store an ordinal tree with n nodes and supports a rich set of basic operations on these trees in $\lg n$ 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 [2]. 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 $64$ cores and likely beyond.

PDF document

An author's version of our work can be downloaded here. The link to the official version is here.

The Code

The code for this work is available at github.

Experiments

• wiki: The Wikipedia dump (January 12, 2015). This input has 498,753,914 parentheses.
• prot: Suffix tree of the protein data from the Pizza&Chili corpus. The suffix tree was constructed using this code. This input has 670,721,006 parentheses.
• dna: Suffix tree of the DNA data from the Pizza&Chili corpus. The suffix tree was constructed using this code. This input has 1,154,482,174 parentheses.
• ctree: Complete binary tree of depth 30. This input has 2,147,483,644 parentheses.
• osm: The OpenStreetMap dump (January 10, 2015). This input has 4,675,776,358 parentheses.

Results

• [1] Navarro, G., Sadakane, K.: Fully functional static and dynamic succinct trees. ACM Trans. Algorithms 10(3), 16:1–16:39 (May 2014)
• [2] Arroyuelo, D., Cánovas, R., Navarro, G., Sadakane, K.: Succinct trees in practice. In: ALENEX. pp. 84–97. SIAM Press, Austin, Texas, USA (2010)