PAM (Parallel Augmented Maps) is an open-source parallel C++ library implementing the interface for sequence, ordered sets, ordered maps, and augmented maps.[1] The library is available on GitHub. It uses the underlying balanced binary tree structure using join-based algorithms.[1] PAM supports four balancing schemes, including AVL trees, red-black trees, treaps and weight-balanced trees.
PAM is a parallel library and is also safe for concurrency. Its parallelism can be supported by cilk, OpenMP or the scheduler in PBBS.[2] Theoretically, all algorithms in PAM are work-efficient and have polylogarithmic depth. PAM uses underlying persistent tree structure such that multi-versioning is allowed. PAM also supports efficient GC.
To define a sequence, users need to specify the key type of the sequence.
PAM supports functions on sequences including construction, find an entry with a certain rank, first, last, next, previous, size, empty, filter, map-reduce, concatenating, etc.
To define an ordered set, users need to specify the key type and the comparison function defining a total ordering on the key type.
On top of the sequence interface, PAM also supports functions for ordered sets including insertion, deletion, union, intersection, difference, etc.
To define an ordered map, users need to specify the key type, the comparison function on the key type, and the value type.
On top of the ordered set interface, PAM also supports functions for ordered maps, such as insertion with combining values.
To define an augmented map, users need to specify the key type, the comparison function on the key type, the value type, the augmented value type, the base function, the combine function and the identity of the combine function.
On top of the ordered map interface, PAM also supports functions for augmented maps, such as aug_range.
In addition to the tree structures, PAM also implements the prefix structure for augmented maps.
The library also provides example implementations for a number of applications, including 1D stabbing query (using interval trees, 2D range query (using a range tree and a sweepline algorithm), 2D segment query (using a segment tree and a sweepline algorithm), 2D rectangle query (using a tree structure and a sweepline algorithm), inverted index searching, etc.
The library has been tested in various applications, including database benchmarks,[3] 2D segment tree,[4] 2D interval tree,[1] inverted index[1] and multiversion concurrency control.[5]
