Paper Info
Title
Implementing parallel and concurrent tree structures.
Abstract
As one of the most important data structures used in algorithm design and programming, balanced search trees are widely used in real-world applications for organizing data. Answering the challenges thrown up by modern large-volume and ever-changing data, it is important to consider parallelism, concurrency, and persistence. This tutorial will introduce techniques for supporting functionalities on trees, including various parallel algorithms, concurrency, multiversioning, etc. In particular, this tutorial will focus on an algorithmic framework for parallel balanced binary trees, which works for multiple balancing schemes, including AVL trees, red-black trees, weight-based trees, and treaps. This framework allows for theoretically-efficient algorithms. The corresponding implementation is available as a library, which demonstrates good performance both sequentially and in parallel in various use scenarios. This tutorial will focus on the following topics: 1) the algorithms and techniques used in the PAM library; 2) the interface of the library and a hands-on introduction to the download/installation of the library; 3) examples of applying the library to various applications and 4) introduction about other useful techniques for parallel tree structures and performance comparisons with PAM.
Year
DOI
Venue
2019
10.1145/3293883.3302576
PPoPP
Keywords
Field
DocType
PAM, augmented map, balanced tree, concurrent, library, ordered map, ordered set, parallel
Ordered set,Data structure,Algorithm design,AVL tree,Parallel algorithm,Computer science,Concurrency,Parallel computing,Binary tree,Tree structure
Conference
ISBN
Citations 
PageRank 
978-1-4503-6225-2
1
0.37
References 
Authors
9
2
Name
Order
Citations
PageRank
Yihan Sun17311.19
Guy E. Blelloch22927207.30