# Fast Parallel Operations on Search Trees

arXiv: https://arxiv.org/abs/1510.05433 · HTML: https://mlsanity.com/paper/1510.05433/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Oct 2015.

## Built on by (most cited first, 1 of 1)

- [Piecewise Linear Approximation in Learned Index Structures: Theoretical and Empirical Analysis](https://mlsanity.com/paper/2506.20139/) (2025)

## Abstract (arXiv)

Using (a,b)-trees as an example, we show how to perform a parallel split with logarithmic latency and parallel join, bulk updates, intersection, union (or merge), and (symmetric) set difference with logarithmic latency and with information theoretically optimal work. We present both asymptotically optimal solutions and simplified versions that perform well in practice - they are several times faster than previous implementations.