PSI is a high-performance parallel library for a collection of spatial indexes -- kd-trees, quad/oct-trees, and 1-D trees over a space-filling curve -- which are:
- 🚀 Blazing fast, and scales to billions of input size,
- 🔀 Highly parallel, achieves almost linear speedup for hundreds of cores,
- 🎳 Supports tree construction, batch updates (with handling of imbalance), and a wide range of queries,
- 📝 Provide strong theoretical guarantees for the running time, parallelism, and I/O (cache) efficiency,
- 🛠️ Easy to adapt, integrate, and deploy.
Note: the prototype of the PSI contains no AI-written code. Later it was refactored using AI to improve the readability and usability. The performance of some indexes are slightly affected but generally they all match the reports in the paper. If you are sensitive to the AI code, please checkout the af67b82 for the original design. Thanks!
- Quick Start
- User Manual
- Docker
- Artifact Evaluation
- How to Pick the Tree 🧐
- Contributing
- Third-party code
If you use our code, please cite our papers:
@inproceedings{men2026dynamic,
author = {Men, Ziyang and Huang, Bo and Gu, Yan and Sun, Yihan},
title = {Parallel Dynamic Spatial Indexes},
year = {2026},
publisher = {Association for Computing Machinery},
address = {New York, NY, USA},
booktitle = {Proceedings of the 31st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming},
location = {Sydney, Australia},
series = {PPoPP '26},
doi = {10.1145/3774934.3786412}
}
@article{men2025parallel,
title={Parallel kd-tree with Batch Updates},
author={Men, Ziyang and Shen, Zheqi and Gu, Yan and Sun, Yihan},
journal={Proceedings of the ACM on Management of Data},
volume={3},
number={1},
pages={1--26},
year={2025},
publisher={ACM New York, NY, USA}
}PSI is MIT licensed — see LICENSE.
It also redistributes third-party code under other terms; see THIRD_PARTY.md.
Have a good day! ☀️