PPoPP '26: Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming. 31 January - 4 February, 2026 Sydney, Australia..
Yiwei Zhao, Hongbo Kang*, Ziyang Men^, Yan Gu^, Guy E. Blelloch, Laxman Dhulipala~, Charles McGuffey†, Phillip B. Gibbons
Carnegie Mellon University
* Tsinghua University
^ University of California, Riverside
~ University of Maryland
† Reed College
Space-partitioning indexes are widely used for managing multi-dimensional data, but their throughput is often memorybottlenecked. Processing-in-memory (PIM), an emerging architectural paradigm, mitigates memory bottlenecks by embedding processing cores directly within memory modules, allowing computation to be offloaded to these PIM cores.
In this paper, we present PIM-zd-tree, the first spacepartitioning index specifically designed for real-world PIM systems. PIM-zd-tree employs a tunable multi-layer structure, with each layer adopting distinct data layouts, partitioning schemes, and caching strategies. Its design is theoretically grounded to achieve load balance, minimal memory-channel communication, and low space overhead. To bridge theory and practice, we incorporate implementation techniques such as practical chunking and lazy counters. Evaluation on a real-world PIM system shows that PIM-zd-tree’s throughput is up to 4.25× and 99× higher than two state-of-the-art shared-memory baselines.
FULL TR: pdf