Work-Efficient Parallel Data Structures with Polylogarithmic Depth

21 concepts6 papers1 proposal

When designing parallel algorithms, researchers are often caught in a tug-of-war between two fundamental metrics: work (the total number of operations performed) and depth (the longest chain of sequential dependencies). A naive parallel algorithm might achieve low depth by aggressively duplicating computations, but this wastes CPU cycles and scales poorly. Conversely, the most efficient sequential algorithms minimize work but process data strictly one element at a time, resulting in a depth equal to the input size ($O(n)$).

The holy grail of parallel computing is to design algorithms that are work-efficient—matching the total operation count of the best sequential alternative—while maintaining polylogarithmic depth ($O(\log^c n)$). Achieving this requires moving away from element-by-element iteration and restructuring data structures around parallel primitives like sorting, batching, and blocking.

Exposing Shallow Dependencies

Many classic algorithms appear inherently sequential because they are framed as a series of incremental steps. For instance, randomized incremental algorithms construct solutions (like Delaunay triangulations or linear programs) by inserting one element at a time and updating the structure.

However, this strict sequential ordering is often an artifact of how the algorithm is described rather than a fundamental constraint of the problem. In Parallelism in Randomized Incremental Algorithms, Guy E. Blelloch demonstrated that many randomized incremental algorithms possess an underlying "shallow dependence structure." By analyzing these dependencies, Blelloch showed that minor modifications to the execution order allow independent elements to be processed simultaneously. This framework proves that we can unlock massive parallelism (polylogarithmic depth) without performing any more total work than the sequential baseline.

Restructuring via Sorting Primitives

To see how this intuition applies to concrete data structures, consider the wavelet tree—a representation crucial for compressed sequence storage and fast rank/select queries. Sequentially, a wavelet tree is built top-down by projecting symbols to left or right children based on their bits.

Instead of processing symbols individually, we can reframe the construction using highly optimized parallel primitives. In Parallel Wavelet Tree Construction, Julian Shun utilized parallel prefix sums, filters, and stable integer sorting to rearrange symbols level by level. Because stable sorting can be executed in parallel with low depth, the entire tree can be constructed in polylogarithmic depth.

Building on this in Improved parallel construction of wavelet trees and rank/select structures, Shun demonstrated that plugging different parallel sorting subroutines into the construction framework allows designers to navigate the trade-offs between work and depth. This approach yields parallel algorithms that match the work complexity of the best sequential methods across varying alphabet sizes, solving a long-standing efficiency bottleneck.

Batching and Blocking for Dynamic Operations

Parallelizing the static construction of a data structure is highly valuable, but maintaining that structure under dynamic updates or memory constraints introduces new challenges. If a single update requires traversing a tree path, concurrent updates risk colliding or creating sequential bottlenecks.

Two core mechanisms resolve this: batching updates and blocking nodes.

Batch-Parallel Updates

Instead of modifying a structure element by element, updates can be collected into large groups and applied all at once. In Batch-Parallel Euler Tour Trees, Tom Tseng et al. applied this to dynamic forest maintenance. By representing trees as cyclic sequences managed via a new batch-parallel skip list, the authors designed algorithms capable of processing large batches of edge additions (links) and removals (cuts) simultaneously. The batching mechanism groups independent structural modifications, achieving asymptotically optimal work and tight depth bounds.

Block-Level Abstractions

When data structures must be compressed to save space, operating on individual bits or elements destroys parallelism. The solution is to group elements into contiguous chunks, or blocks.

In PaC-trees: Supporting Parallel and Compressed Purely-Functional Collections, Laxman Dhulipala et al. et al. introduced a hybrid structure that combines purely-functional trees with compressed leaf blocks. By redefining fundamental tree primitives to operate on block-level transitions rather than single elements, the authors allowed complex parallel algorithms to be reused seamlessly across compressed formats. This abstraction delivers significant memory reductions while maintaining near-linear parallel speedups.

This philosophy of using structural blocks to facilitate parallel updates dates back to early parallel problems like the Relational Coarsest Partition Problem (RCPP). Insup Lee 0001 et al. introduced the XARRAY structure to handle parallel block splitting and merging. Their work proved that specialized, block-aware data structures are essential for unlocking polylogarithmic or near-linear parallel execution times in dynamically manipulated systems.

Summary

Work-efficient, low-depth parallel data structures work because they replace fine-grained sequential dependencies with coarse-grained parallel operations. Whether by exposing shallow dependencies in incremental algorithms, leveraging parallel stable sorting to build trees level-by-level, or grouping updates into batches and blocks, these techniques ensure that multi-core processors spend their time doing useful work rather than waiting on sequential bottlenecks.

Key Foundational Work

Parallel Wavelet Tree Construction (2015) — contributed 6 concept elements to this direction.
Parallel Algorithms for Relational Coarsest Partition Problems (1998) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_work_efficient_parallel_rank_select_cons_26a975b4,
  title = {work-efficient parallel rank/select construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/work-efficient-parallel-rank-select-construction/rdr_26a975b4f34d4714bce6d43536119050},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_work_efficient_parallel_rank_select_cons_26a975b4_v1,
  title = {work-efficient parallel rank/select construction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/work-efficient-parallel-rank-select-construction/rdr_26a975b4f34d4714bce6d43536119050/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake