Parallel Augmented Maps
Questions?
Contact: syhlalala at gmail dot com

Prerequisites

PAM can be compiled with g++ 5.4.0 or later versions with support for Cilk Plus.

Getting Started

Download the code if you have not already. The library is located in the directory c++. The library also provides example codes.

c++ : The library
common : The implementation for prefix structures
interval : The implementation for 1D stabbing query / report-all query.
Containing an interval tree.
range_query : The implementation for 2D point containment counting query / report-all query.
Containing a range tree and two sweepline algorithms.
rectangle : The implementation for 2D rectangle stabbing counting query / report-all query.
Containing two tree structures and two sweepline algorithms.
segment : The implementation for 2D segment intersection counting query / report-all query.
Containing two tree structures and two sweepline algorithms.
tests : General tests.

To run a simple test in PAM. Try the following:

$ cd test
$ make
$ ./aug_sum [-n size1] [-m size2] [-r rounds] <testid>

For example,

$ ./aug_sum 4 -n 100000000 -m 100000000 -r 5

will test the performance of combining two trees (union) both of size 1000000000 for 5 rounds. We recommend to use numactl -i all for all test cases.

Users can also adjust the number of working threads by:

export CILK_NWORKERS=<num_threads>