Fuentes-Sepúlveda, JoséFerres, LeoHe, MengZeh, Norbert2018-02-232018-02-232017Fuentes-Sepúlveda, José; Ferres, Leo; He, Meng; Zeh, Norbert (2017). Parallel construction of succinct trees,.Theoretical Computer Science Volume 700, 14 November 2017, Pages 1-22http://hdl.handle.net/11447/1999https://doi.org/10.1016/j.tcs.2017.07.025Succinct representations of trees are an elegant solution to make large trees fit in main memory while still supporting navigational operations in constant time. However, their construction time remains a bottleneck. We introduce two parallel algorithms that improve the state of the art in succinct tree construction. Our results are presented in terms of work, the time needed to execute a parallel computation using one thread, and span, the minimum amount of time needed to execute a parallel computation, for any amount of threads. Given a tree on n nodes stored as a sequence of balanced parentheses, our first algorithm builds a succinct tree representation with O(n) work, O(lg⁡n) span and supports a rich set of operations in O(lg⁡n) time. Our second algorithm improves the query support. It constructs a succinct representation that supports queries in O(c) time, taking O(n+nlgc⁡nlg⁡(nlgc⁡n)+cc) work and O(c+lg⁡(ncclgc⁡n)) span, for any positive constant c. Both algorithms use O(nlg⁡n) bits of working space. In experiments using up to 64 cores on inputs of different sizes, our first algorithm achieved good parallel speed-up. We also present an algorithm that takes O(n) work and O(lg⁡n) span to construct the balanced parenthesis sequence of the input tree required by our succinct tree construction algorithm.22 p.en-USSuccinct data structureSuccinct tree constructionMulticoreParallel algorithmArtículo