Parallel construction of succinct trees

Simple item page
dc.contributor.authorFuentes-Sepúlveda, José
dc.contributor.authorFerres, Leo
dc.contributor.authorHe, Meng
dc.contributor.authorZeh, Norbert
dc.date.accessioned2018-02-23T16:52:18Z
dc.date.available2018-02-23T16:52:18Z
dc.date.issued2017
dc.description.abstractSuccinct 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.
dc.description.versionVersión Publicada
dc.format.extent22 p.
dc.identifier.citationFuentes-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-22
dc.identifier.urihttp://hdl.handle.net/11447/1999
dc.identifier.urihttps://doi.org/10.1016/j.tcs.2017.07.025
dc.language.isoen_US
dc.subjectSuccinct data structure
dc.subjectSuccinct tree construction
dc.subjectMulticore
dc.subjectParallel algorithm
dc.titleParallel construction of succinct trees
dc.typeArtículo

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Parallel construction of succinct trees.pdf
Size:
907.16 KB
Format:
Adobe Portable Document Format
Description:
Texto completo
Download

Collections

Artículos Ingeniería

Implementado por OpenGeek Services