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 x to 73 x, but end-to-end speedup is lower, ranging from 0.87 x to 11.29 x. 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 x on Lakes. These findings motivate parallel host-side aggregation, efficient result handling, and query-aware DPU assignment for scalable PIM-based spatial search.

Department(s)

Computer Science

Publication Status

Free Access

Comments

National Science Foundation, Grant 2344578

Keywords and Phrases

communication overhead; load balancing; Processing-in-Memory; R-tree; spatial query processing; UPMEM

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 2026 The Author(s), All rights reserved.

Creative Commons Licensing

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.

Publication Date

13 Jul 2026

Download

Full Text Link

Share

 
COinS