PAM library
PAM (Parallel Augmented Maps) is a parallel C++ library implementing the interface for sequence, ordered sets, ordered maps and augmented maps[1]. 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. The parallelism is supported by cilk. 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.
Interface
Sequences
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.
Ordered sets
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.
Ordered sets
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.
Augmented maps
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.
Implementation for Example Applications
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.
References
External links
- PAM, the parallel augmented map library.