PPoPP 2026
Sat 31 January - Wed 4 February 2026 Sydney, Australia
co-located with HPCA/CGO/PPoPP/CC 2026
Mon 2 Feb 2026 14:50 - 15:10 at Pyrmont - Concurrent Data Structures Chair(s): Calin Cascaval

Augmentation makes search trees tremendously more versatile, allowing them to support efficient aggregation queries, order-statistic queries, and range queries in addition to insertion, deletion, and lookup. In this paper, we present the first lock-free augmented balanced search tree supporting generic augmentation functions. Our algorithmic ideas build upon a recent augmented unbalanced search tree presented by Fatourou and Ruppert [DISC, 2024]. We implement both data structures, solving some memory reclamation challenges in the process, and provide an experimental performance analysis of them. We also present optimized versions of our balanced tree that use delegation to achieve better scalability and performance (by more than 2x in most workloads). Our experiments show that our augmented balanced tree completes updates 2.2 to 30 times faster than the unbalanced augmented tree, and outperforms unaugmented trees by up to several orders of magnitude on 120 threads.

Mon 2 Feb

Displayed time zone: Hobart change

14:10 - 15:30
Concurrent Data StructuresMain Conference at Pyrmont
Chair(s): Calin Cascaval Google DeepMind
14:10
20m
Talk
UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic TreesBest Paper Nominee
Main Conference
Quinten De Man University of Maryland, Atharva Sharma University of Maryland, Kishen N Gowda University of Maryland, Laxman Dhulipala University of Maryland, College Park
DOI
14:30
20m
Talk
Sharded Elimination and Combining for Highly-Efficient Concurrent Stacks
Main Conference
Ajay Singh FORTH ICS, Nikos Metaxakis , Panagiota Fatourou FORTH ICS and University of Crete, Greece
DOI
14:50
20m
Talk
Concurrent Balanced Augmented Trees
Main Conference
Evan Wrench University of British Columbia, Ajay Singh FORTH ICS, Younghun Roh Massachusetts Institute of Technology, Panagiota Fatourou University of Crete & FORTH, Siddhartha Jayanti Google Research, Eric Ruppert York University, Yuanhao Wei University of British Columbia
DOI
15:10
20m
Talk
Parallel Dynamic Spatial Indexes
Main Conference
Ziyang Men University of California, Riverside, Bo Huang University of California, Riverside, Yan Gu University of California, Riverside, Yihan Sun University of California, Riverside
DOI