¯_(ツ)_/¯ The answer is all about the operation you need: whether it is update-heavy or query-heavy.
Baselines:
- Pkd-tree: the SOTA parallel kd-tree;
- P-Orth tree: parallel orth-trees (known as the quad-tree in 2d and oct-tree in 3d);
- SPaC-H: parallel self-balanced 1d-tree using Hilbert code to order points;
- SPaC-Z: similar with SPaC-H but use Morton code instead;
- CPAM-H/Z: another 1d-tree based on the parallel augmented map;
- Zd-tree: yet another 1d-tree based on the Morton code;
- BHL-tree: a plain parallel kd-tree.
- Log-tree: a parallel kd-tree using logarithmic layout.
Benchmark:
- Uniform: points are uniformly distributed across the cube;
- Sweepline: points are ordered by a certain dimension;
- Varden: points have very skewed distribution.