TL;DR
PaC-trees (Parallel Compressed trees) introduce a hybrid data structure that combines the safety and parallelism of purely-functional trees with the memory efficiency of compressed arrays. By "blocking" leaf nodes and applying difference encoding, the authors achieve up to an 8x reduction in memory usage while matching or exceeding the performance of state-of-the-art functional libraries.
What Problem Does This Paper Address?
In modern data processing, "purely-functional" data structures are highly desirable. Because they are immutable, they are inherently thread-safe and allow for "instant" snapshots—you can keep a version of a database for analysis while a stream of updates continues on a new version without complex locking.
However, there is a "space tax." Standard functional trees (like those in the PAM library) store every single element in its own tree node. This creates massive overhead: for every 8-byte integer you store, you might spend 24–32 bytes on pointers and metadata. For large-scale analytics (like graph processing or search indices), this overhead often makes functional approaches impractical compared to "static" compressed arrays. The challenge is: how do we get the memory density of a compressed array without losing the flexible, parallel-friendly nature of a tree?
Methods
The authors introduce PaC-trees and an associated C++ library called CPAM. The core innovation is a structural shift:
- Blocked Leaves: Instead of a standard Binary Search Tree (BST) where every leaf is a single element, PaC-trees use "flat nodes." These are contiguous arrays containing between $B$ and $2B$ elements (where $B$ is a tunable parameter, typically 128).
- Difference Encoding (DE): Within these blocks, the library can compress sorted integer keys by storing only the differences (deltas) between consecutive elements. This exploits the fact that sorted data often has small gaps, which can be represented in fewer bits.
- The Join-Based Framework: Most tree operations (union, intersect, filter) are implemented using a "join" primitive. The authors redesigned
joinandexpose(the function that splits a node) to handle the transition between internal nodes and compressed blocks transparently. This allows high-level algorithms to remain unchanged while the underlying structure handles the compression. - Efficient Augmentation: Functional trees often store "augmented" values (like the sum or maximum of a subtree) at every node. PaC-trees only store one augmented value per block, further slashing memory overhead.
Datasets
The authors evaluated CPAM against several baselines (PAM, Aspen, and Intel’s Parallel STL) using:
- Microbenchmarks: Synthetic sets, maps, and sequences of $10^8$ elements.
- Inverted Indices: A Wikipedia corpus containing 1.94 billion words across 8.13 million documents.
- Graph Processing: Several massive real-world graphs, including Twitter (2.4B edges) and Friendster (3.6B edges).
- Geometric Data: 100 million 2D points for range query benchmarks.
Key Insights and Ideas
- The "Sweet Spot" of Blocking: By moving the "functional" boundary from individual elements to blocks of elements, the authors eliminate the vast majority of pointer overhead. For $B=128$, only about 1% of the memory is spent on tree metadata.
- Cache Locality: Standard trees involve pointer-chasing, which is slow. By storing elements in blocks (arrays), PaC-trees significantly improve cache performance during scans and filters.
- Algorithmic Transparency: One of the most elegant parts of the paper is that by carefully redefining the
joinandsplitprimitives, they didn't have to rewrite complex parallel algorithms likeunion. The "blocking" logic is encapsulated at the lowest level. - Deterministic Compression: Unlike some previous compressed tree structures (like C-trees in Aspen) that rely on randomization, PaC-trees are deterministic, providing more consistent theoretical bounds on work and space.
Key Results
- Memory Efficiency: CPAM consistently uses about 1/4 the space of the PAM library for uncompressed data. When difference encoding is enabled, it uses 2.1x to 7.8x less space than PAM.
- Performance: Despite the overhead of compressing/decompressing blocks, CPAM is often faster than PAM because the reduced memory footprint leads to fewer cache misses.
- Graph Superiority: Compared to Aspen (a state-of-the-art graph streaming system), CPAM is 1.6x faster at batch updates while using 1.3x to 2.6x less memory.
- Scalability: The system demonstrates excellent parallel scaling, achieving up to 100x speedup on a 72-core machine for various primitives.
Limitations and Future Work
- Single-Point Update Cost: Because elements are stored in blocks, inserting a single element requires re-processing an entire block ($O(B + \log n)$). While the authors propose an "in-place" update version to mitigate this, it sacrifices some of the purity of the functional model.
- Internal Node Fan-out: The current implementation uses binary trees for the internal structure. The authors suggest that moving to a higher fan-out (like a B-tree) for the internal nodes could further reduce the number of cache misses during lookups.
- Non-Volatile Memory: The authors identify exploring PaC-trees on new hardware, such as persistent/non-volatile memory, as a promising direction for future research.
Summary updated