Parallel Augmented Maps
Contact: syhlalala at gmail dot com
  • This is a wild balanced binary tree. In fact, it is named hyphaene compressa, or the East African doum palm.

  • All algorithms in PAM are based on a single primitive Join. Except Join, all the other algorithms are generic across balancing schemes.
  • The tree structure has several good properties, which are essential for efficiently processing big data.

PAM (Parallel Augmented Maps)

A Parallel C++ Library for Balanced Binary Trees

  • Supports efficient parallel (augmented) balanced binary trees.
  • Provides a simple and effective interface for abstract data types (ADTs) including sequences, ordered sets, ordered maps and augmented maps.
  • Uses multi-core parallelism supported by Cilk.
  • Supports four different balancing schemes: AVL trees, red-black trees, weight-balanced trees, and treaps.
  • Adopts a simple algorithmic framework: the join-based algorithms.
  • Is fast both sequentially and in parallel.

Download Tutorial Abstract

Conference Papers


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.