Full Featured

PAM supports commonly-used functions including insertion, deletion, lookup, union, intersection, difference, map-reduce, filter, range, etc., for four balancing schemes.

Theoretically Efficient

All algorithms in PAM are asymptotically work-efficient (sequentially optimal) with polylogarithmic parallel depth.

Highly Parallelized

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.

Persistent

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.

Multi-version Concurrency Control

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.

Garbage Collection

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.

Simple & Generic Algorithms

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.

Framework for Augmentation

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.

Extendable to Various Applications

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.

Yihan Sun

Yihan Sun is currently a Ph.D. student at CMU working on parallel algorithms. Homepage

Guy E. Blelloch

Guy Blelloch is a professor, and the Associate Dean for Undergraduate Programs at CMU. Homepage

Daniel Ferizovic

Daniel Ferizovic was involved in this work when he was a student intern at CMU.