Challenges in Scaling R-tree Spatial Search on Processing-In-Memory

Abstract

Spatial query processing is important in scientific, geospatial, and data-intensive applications. R-trees are widely used to index spatial objects, but their query-dependent traversal creates irregular work across different regions. This poster studies the challenges of scaling R-tree spatial search on a commercial Processing-in-Memory (PIM) system. Although PIM reduces CPU to memory data movement by executing search near memory, it does not remove full-pipeline overheads: the host still manages data placement, query batching, kernel launches, result retrieval, and aggregation. Our results show strong DPU-side search acceleration, with PIM kernel speedup ranging from about 20 × to 73 × , but end-to-end speedup is lower, ranging from 0.87 × to 11.29 ×. The runtime breakdown shows that CPU-side aggregation can dominate output-heavy workloads; on the Buildings dataset, aggregation accounts for 62.9% of total time, while DPU kernel time is only 4.4%. DPU-count scaling shows that more DPUs speed up the kernel, but end-to-end gains saturate due to full-pipeline overheads. We also observe a workload imbalance across the DPUs, with the ratio of maximum to mean hits reaching 29.1 × on Lakes. These findings motivate parallel host-side aggregation, efficient result handling, and query-aware DPU assignment for scalable PIM-based spatial search.