PAM supports commonly-used functions including insertion, deletion, lookup, union, intersection, difference, map-reduce, filter, range, etc., for four balancing schemes.
All algorithms in PAM are asymptotically work-efficient (sequentially optimal) with polylogarithmic parallel depth.
PAM uses fork-join parallelism supported by Cilk. All algorithms have polylogarithmic parallel depth and have been shown to be scalable to more than 100 working threads. All tested algorithms in PAM achieve good parallel self-speedup in practice.
PAM implements fully-persistent tree structures using path-copying, meaning that any update on the tree structure will not destruct the old tree structure but yield a new version. The trees are also strongly-immutable or functional.
MVCC in PAM is supported based on persistence. Any number of threads can access the tree concurrently safely, working on a snapshot. The multi-versioning is achieved via snapshots. For supporting serializability, batching with a single writer is recommended. Other version-control algorithms can be applied. E.g., aborting when detecting conflicts.
PAM uses reference counting for fine-grained garbage collection. The garbage collector will only free the tree nodes only appearing in the to-be-collected version, while keeping those shared with other versions. The garbage collection algorithm also runs in parallel.
PAM uses the Join-based algorithm framework. Except Join all the other algorithms are generic across multiple balancing schemes (four implemented in PAM: AVL trees, red-black trees, weight-balanced trees, and treaps). The algorithms are also simple and PAM has light-weighted code.
PAM support an abstract framework for augmentations through C++ template. The framework is formalized as the augmented map, which is an abstract data type extending ordered (key-value) maps. PAM support two data structures for augmented maps: augmented trees and prefix structures.
PAM supports clean general-purpose interface such that many applications can be implemented directly on top of PAM. The library provides example code for applications in computational geometry (e.g., range trees) and inverted index searching. PAM has also been applied to graph processing systems and database management systems. Making use of PAM simplifies coding and greatly reduces the number of lines of code.
Join-based algorithms and proofs for bounds.
Implementation details of the library and the formalization of augmented maps.
Applied to computational geometry algorithms.
Applied to multi-version concurrency control with effective garbage collection.
Yihan Sun is currently a Ph.D. student at CMU working on parallel algorithms.
Guy Blelloch is a professor, and the Associate Dean for Undergraduate Programs at CMU.
Daniel Ferizovic was involved in this work when he was a student intern at CMU.
We thank the PBBS team because PAM uses several building blocks in PBBS.
We also would like to thank Laxman Dhulipala and Joana Fonseca for reporting several bugs in the library.