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.
Interface edit
Sequences edit
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 edit
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 maps edit
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 edit
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 edit
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.
Used in applications edit
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]
References edit
- ^ a b c d Sun, Yihan; Ferizovic, Daniel; Belloch, Guy E. (23 March 2018). "PAM: parallel augmented maps". ACM SIGPLAN Notices. 53 (1): 290–304. doi:10.1145/3200691.3178509. ISSN 0362-1340. Retrieved 5 September 2020.
- ^ Problem Based Benchmark Suite Library
- ^ Sun, Yihan; Blelloch, Guy E.; Lim, Wan Shen; Pavlo, Andrew (1 October 2019). "On supporting efficient snapshot isolation for hybrid workloads with multi-versioned indexes". Proceedings of the VLDB Endowment. 13 (2): 211–225. doi:10.14778/3364324.3364334. ISSN 2150-8097. S2CID 204841857.
- ^ Sun, Yihan; Blelloch, Guy E. (1 January 2019). "Parallel Range, Segment and Rectangle Queries with Augmented Maps". 2019 Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics: 159–173. arXiv:1803.08621. doi:10.1137/1.9781611975499.13. ISBN 978-1-61197-549-9.
- ^ Ben-David, Naama; Blelloch, Guy E.; Sun, Yihan; Wei, Yuanhao (17 June 2019). "Multiversion Concurrency with Bounded Delay and Precise Garbage Collection". The 31st ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery. pp. 241–252. doi:10.1145/3323165.3323185. ISBN 9781450361842.
External links edit
- PAM, the parallel augmented map library.