CPMA: An Efficient Batch-Parallel Compressed Set Without Pointers

This paper introduces the batch-parallel Compressed Packed Memory Array (CPMA), a compressed dynamic ordered batch-parallel set data structure based on the Packed Memory Array (PMA). Traditionally, batch-parallel sets are built on pointer-based data structures such as trees because pointer-based structures enable fast parallel unions via pointer manipulation. When compared to cache-optimized trees, PMAs were slower to update but faster to scan. The batch-parallel CPMA overcomes this tradeoff between updates and scans by optimizing for cache-friendliness. On average, the CPMA is faster than compressed PaC-trees, a state-of-the-art batch-parallel set library based on cache-optimized trees, by 1.2x on range queries and 3x on batch updates. We further evaluate the CPMA compared to compressed PaC-trees on a real-world application of dynamic graph processing. The CPMA is on average 1.2x faster on a suite of graph algorithms and 2x faster on batch inserts for graphs when compared with compressed PaC-trees.