# GPU-friendly, Parallel, and (Almost-)In-Place Construction of Left-Balanced k-d Trees

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

## Key facts

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

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

- [A Generalizable Light Transport 3D Embedding for Global Illumination](https://mlsanity.com/paper/2510.18189/) (2025)
- [GraphGP: Scalable Gaussian Processes with Vecchia's Approximation](https://mlsanity.com/paper/2606.11402/) (2026)

## Abstract (arXiv)

We present an algorithm that allows for building left-balanced and complete k-d trees over k-dimensional points in a trivially parallel and GPU friendly way. Our algorithm requires exactly one int per data point as temporary storage, and uses O(log N) iterations, each of which performs one parallel sort, and one trivially parallel CUDA per-node update kernel.