Augmented map

In computer science, the augmented map is an abstract data type (ADT) based on ordered maps, which associates each ordered map an augmented value. For an ordered map formula_1 with key type formula_2, comparison function formula_3 on formula_2 and value type formula_5, the augmented value is defined based on two functions: a "base" function formula_6 and a "combine" function formula_7, where formula_8 is the type of the augmented value. The base function formula_9 converts a single entry in formula_1 to an augmented value, and the combine function formula_11 combines multiple augmented values. The combine function formula_11 is required to be associative and have an identity formula_13 (i.e., formula_14 forms a monoid). We extend the definition of the associative function formula_11 as follows:
 formula_16
 formula_17
 formula_18
Then the augmented value of an ordered map formula_19 is defined as follows:
 formula_20
Accordingly, an augmented map can be formally defined as a seven-tuple formula_21. For example, an augmented map with integral keys and values, on which the augmented value is defined as the sum of all values in the map, is defined as:
 formula_22
As an abstract data type, the augmented map is often used to model problems and serves as an abstraction with a useful interface. It is designed for supporting fast range sums, which means to quickly return the augmented value of all entries in a certain key range.
Interface.
In addition to the interface for a standard ordered map, the augmented map should also support functions for range sums. In particular:
Some functions, although are not defined based on augmented values, can make use of augmented values to accelerate their algorithms. Usually, they would require some certain representation of augmented maps, and certain conditions for input parameters.
are themselves maps or other large data structures. It allows projecting the augmented values down onto another type by formula_47 (e.g. project augmented values with complicated structures to values like their sizes) then summing them by formula_48, and is much more efficient when applicable.
Implementation.
Augmented Trees.
The augmented map can be supported efficiently by augmented trees, where each tree node is augmented by the augmented value of all entries in its subtree. Because of the associativity of the combine function formula_11, the augmented value of a certain tree is fixed, and is independent of the shape of the tree, regardless of rotations. In this case, by combining the partial sums in the tree nodes, any range sum can be returned in formula_50 time on an augmented map of size formula_51, assuming both formula_11 and formula_9 have constant cost.
For aug_filter, the tree structure takes the advantage that if the augmented value of a subtree does not satisfy the indicator formula_54, the whole tree gets discarded. In this case, the cost of aug_filter is formula_55 where formula_25 is the output size.
For aug_project, whenever a whole subtree falls in the range formula_31, its augmented value can be directly combined to the result, instead of requiring traversing the tree.
Prefix Structures.
Another implementation is to use prefix structures, which stores the augmented value of all prefixes of the map. For the above-defined augmented map formula_58, the prefix structure is an array stored the prefix sum of the values, sorted by their keys.
Prefix structures are particularly useful for aug_left, but can be inefficient to implement other functions on the augmented map interface. It can be useful in some geometric algorithms.
Example Application.
1D stabbing query.
A 1D stabbing query takes as input a set of intervals on 1D number line. The query asks for if a given point is covered by any input interval, or all intervals covering this point. An augmented map can be defined for this problem, where the keys are the left endpoints of all intervals, values are the corresponding right endpoints, and the augmented value is the maximum value of all right endpoints in the map. More formally:
 formula_59
To report if any interval covers a given point formula_60, the query algorithm simply determines if aug_leftformula_61. This is because aug_left looks at all intervals that start before formula_60, and if the maximum right endpoint among them exceeds formula_60, then formula_60 must be covered.
When implemented with augmented trees, the augmented map formula_65 is exactly an interval tree. Constructing such an augmented tree structure costs work formula_66, formula_50 parallel depth and formula_68 space. Each stabbing query can be done in time formula_50.
2D range query.
A 2D range query takes as input a set of points on 2 dimensions. The query asks for all points (or the number) in a certain rectangle, whose edges are parallel to the axis. An augmented map can be defined for this problem, which is a two-level nested map structure. The outer map stores all points and sort them by their x-coordinates. The augmented value of the outer map is an inner augmented map structure, which stores the same set of points as the outer map, but sorts them by their y-coordinates. The augmentation of the inner trees accumulate the count of points, i.e., the augmented value of an inner map is its size. Accordingly, the combine function of the outer map is to take a union of the two inner augmented maps. More formally:
 formula_70
 formula_71
Here for simplicity, assume all coordinates are unique. formula_72 and formula_73 are the types of the x- and y-coordinates.
To answer the range query in rectangle formula_74, the query algorithm extracts the augmented value of the outer map in the key range formula_75, which is an inner map of all desired points sorted by y-coordinates. Therefore, the algorithm takes another aug_range on this inner map and gets the result. For counting queries, the algorithm can make use of the aug_project function.
 formula_76
 formula_77
If the both the inner and the outer maps are implemented by augmented trees, then the whole two-level map structure becomes a range tree structure. If the inner map is supported by the augmented tree structure, and the outer tree is supported as the prefix structure, then the algorithm becomes a sweepline algorithm.
Other examples.
Other examples include segment queries, inverted index searching, rectangle queries, etc.
Libaray support.
A parallel implementation of the augmented map interface is provided in a library PAM.