DSpace Repository :: Browsing by Author "Zeh, Norbert"

Now showing 1 - 1 of 1

Parallel construction of succinct trees
(2017) Fuentes-Sepúlveda, José; Ferres, Leo; He, Meng; Zeh, Norbert
Succinct 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.