  Ordered (key-value) maps are an important and widely-used data type for
large-scale data processing frameworks. Beyond simple search, insertion and
deletion, more advanced operations such as range extraction, filtering, and
bulk updates form a critical part of these frameworks.
  We describe an interface for ordered maps that is augmented to support fast
range queries and sums, and introduce a parallel and concurrent library called
PAM (Parallel Augmented Maps) that implements the interface. The interface
includes a wide variety of functions on augmented maps ranging from basic
insertion and deletion to more interesting functions such as union,
intersection, filtering, extracting ranges, splitting, and range-sums. We
describe algorithms for these functions that are efficient both in theory and
practice.
  As examples of the use of the interface and the performance of PAM, we apply
the library to four applications: simple range sums, interval trees, 2D range
trees, and ranked word index searching. The interface greatly simplifies the
implementation of these data structures over direct implementations.
Sequentially the code achieves performance that matches or exceeds existing
libraries designed specially for a single application, and in parallel our
implementation gets speedups ranging from 40 to 90 on 72 cores with 2-way
hyperthreading.
