# Parallel Batch-Dynamic kd-Trees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2021.

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

- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Monitoring Robustness and Individual Fairness](https://mlsanity.com/paper/2506.00496/) (2025)

## Abstract (arXiv)

kd-trees are widely used in parallel databases to support efficient neighborhood/similarity queries. Supporting parallel updates to kd-trees is therefore an important operation. In this paper, we present BDL-tree, a parallel, batch-dynamic implementation of a kd-tree that allows for efficient parallel k-NN queries over dynamically changing point sets. BDL-trees consist of a log-structured set of kd-trees which can be used to efficiently insert or delete batches of points in parallel with polylogarithmic depth. Specifically, given a BDL-tree with n points, each batch of B updates takes O(Blog2(n+B)) amortized work and O(log(n+B)loglog(n+B)) depth (parallel time). We provide an optimized multicore implementation of BDL-trees. Our optimizations include parallel cache-oblivious kd-tree construction and parallel bloom filter construction. Our experiments on a 36-core machine with two-way hyper-threading using a variety of synthetic and real-world datasets show that our implementation of BDL-tree achieves a self-relative speedup of up to 34.8× (28.4× on average) for batch insertions, up to 35.5× (27.2× on average) for batch deletions, and up to 46.1× (40.0× on average) for k-nearest neighbor queries. In addition, it achieves throughputs of up to 14.5 million updates/second for batch-parallel updates and 6.7 million queries/second for k-NN queries. We compare to two baseline kd-tree implementations and demonstrate that BDL-trees achieve a good tradeoff between the two baseline options for implementing batch updates.