Parallel R-tree–based Spatial Query Processing on a Commercial Processing-in-Memory System Tasmia Jannat1 , Michael Gowanlock2 , Satish Puri1 1
arXiv:2604.14445v1 [cs.DB] 15 Apr 2026
Department of Computer Science Missouri University of Science and Technology, Rolla, MO, USA 2 School of Informatics, Computing, and Cyber Systems Northern Arizona University, Flagstaff, AZ, USA [email protected], [email protected], [email protected]
Abstract—The growing volume of data in scientific domains has made spatial query processing increasingly challenging due to high data transfer costs across the memory hierarchy and limited memory bandwidth. To address these bottlenecks and reduce the energy consumed on data movement, this work explores Processing-in-Memory (PIM) systems by executing range queries directly inside memory chips. Unlike prior PIM studies centered on linear scans or hash-based queries, this work is the first to map R-tree range queries onto commercial PIM hardware. The proposed broadcast-based method constructs the R-tree bottomup on the CPU, broadcasts top levels to UPMEM DPUs (DRAM Processing Units) for global filtering, and distributes lower levels for parallel batched queries in a CPU–DPU system. We evaluate our approach on two real spatial datasets Sports (999K rectangles) and Lakes (8.4M rectangles) and assess scalability using a synthetic dataset with up to 16M rectangles and 3.9M queries, on a commercial UPMEM PIM system with up to 2,540 DPUs. Across all datasets, broadcast-based execution consistently outperforms subtree partitioning by preventing communication from dominating execution. On the Lakes dataset, strong scaling from 512 to 2,540 DPUs reduces kernel time from 64.9 s to 17.6 s, yielding up to 3.66× kernel and 2.70× end-to-end speedup relative to the CPU R-tree search on the same system. The PIM kernel also consumes approximately 3.4× less energy than the corresponding CPU search (e.g., 59.6 kJ vs. 167.0 kJ on Lakes), demonstrating scalable and energy-efficient hierarchical spatial range queries. Index Terms—Range Search, Processing-in-Memory (PIM), High-Performance Computing (HPC), Spatial Query Processing, R-tree Structure
I. I NTRODUCTION HPC systems face significant challenges in handling the exponential increase in data, especially in applications such as Geographic Information Systems (GIS) and spatial databases, which require efficient spatial query processing. Traditional computing architectures struggle because they face the memory wall problem [1], the widening gap between processor speed and memory access, which hinders performance for data intensive tasks. This has led to interest in Processingin-Memory (PIM) architectures that bring computation closer to the data, reducing bottlenecks, and improving both speed and energy efficiency. This limitation is especially evident in spatial query processing. Many scientific and geospatial workloads issue large numbers of range queries over rectangles and polygons. While R-tree indexing reduces the number of
candidate objects examined, the cost of accessing index nodes and data records from memory frequently dominates both performance and energy consumption. PIM offers a direct solution by executing computations near data. Among available platforms, UPMEM DPUs [2], [3] are notable for scale, programmability, and availability in server configurations, which makes them attractive for experiment driven systems work. Most prior PIM evaluations focus on scans and hash based operators [4], [5], [6]. In contrast, little is known about how a hierarchical spatial index such as the R-tree behaves on real PIM hardware, especially when the index is built on the host CPU and traversed across thousands of near memory cores with explicit host to device transfers and small local memories. This paper addresses this gap by presenting the first design and implementation of R-tree range query on a commercial PIM platform. We introduce a broadcast-based execution strategy that serializes and broadcasts compact upper-level R-tree headers to all DPUs for global pruning, while partitioning leaf nodes across DPUs for parallel processing. Queries are broadcast in batches, and each DPU applies upper-level filtering using the locally available R-tree headers before scanning its assigned leaf nodes, thereby preserving hierarchical pruning while minimizing communication and redundant data movement. We evaluate our design on real and synthetic spatial datasets using a commercial UPMEM PIM system with thousands of DPUs. The results show that the proposed broadcast-based execution consistently outperforms subtree-based partitioning by preventing communication from dominating execution. Compared to CPU-based spatial search on the same system, our approach achieves substantial performance improvements and significantly lower energy consumption during the query phase. These findings indicate that hierarchical spatial query processing can be executed efficiently on PIM architectures when index layout and communications are carefully aligned with hardware constraints. We make the following contributions: 1) A heterogeneous CPU–PIM design for hierarchical spatial query processing. We develop a CPU–DPU execution pipeline that constructs and serializes an Rtree on the CPU, broadcasts the upper levels to all DPUs,
and distributes the leaf level in contiguous breadth-first partitions across ranks. 2) First R-tree implementation on commercial Processing-In-Memory architecture. To our knowledge, this is the first study to map R-tree traversal onto a real PIM platform. The design broadcasts the top-level tree structure to all DPUs and distributes leaf partitions across DPUs to expose parallelism. 3) An empirical study of performance and energy on real workloads. We evaluate our design on two real spatial datasets (Sports and Lakes) and a large synthetic dataset with up to 16M rectangles and 3.99M queries, using up to 2,540 DPUs. Our study analyzes kernel-level and end-to-end performance, demonstrating up to 3.6× kernel speedup and 2.7× end-to-end speedup over the CPU search phase on the same system, along with up to 3.4× lower energy consumption for the PIM kernel. Overall, this work shows that hierarchical spatial query processing can be effectively supported on commercial PIM systems through hardware-aware index organization and communication design. By presenting the first implementation and evaluation of R-tree–based spatial query processing on a real PIM platform, the proposed approach highlights the potential of PIM architectures for accelerating irregular, data-intensive workloads beyond linear scans and hash-based operators. II. BACKGROUND AND M OTIVATION A. PIM System Architecture and Model PIM architectures integrate simple processing elements directly within memory chips, enabling computation to be performed close to data and reducing costly data movement across the memory hierarchy [7]. Figure 1 shows the UPMEM processing in memory system that has been used in our work. Each DIMM contains 16 PIM chips, and each chip integrates 8 DRAM Processing Units (DPUs) running at 400 MHz, resulting in 128 DPUs and 8 GB of DRAM capacity per DIMM. At server scale, a 20-DIMM configuration provides up to 2,560 DPUs and 160 GB of memory, enabling thousands of near-memory cores to operate in parallel.
Fig. 1: Processing-in-Memory (PIM) System Organization [8]. DPU stands for DRAM Processing Unit. Each DPU integrates a lightweight processing core and a hierarchical memory system consisting of MRAM, WRAM, and instruction memory (IRAM). MRAM provides 64 MB of DRAM-based storage per DPU and is optimized for bulk accesses, making it suitable for large data structures such as serialized index nodes and leaf records. WRAM is a small
(64 KB), low-latency memory shared among tasklets and is used for control metadata, query buffers, and intermediate results. IRAM stores DPU instructions and is managed by the runtime. DPUs support multiple lightweight hardware threads (tasklets); in the UPMEM PIM v1B platform used in this work, each DPU supports up to 16 tasklets, enabling intraDPU parallelism under tight WRAM constraints. DPUs do not support direct inter-DPU communication; all data exchange occurs via the host using explicit bulk transfers. Consequently, applications follow a bulk-synchronous parallel (BSP) execution model [8], which favors communicationefficient designs that exploit local MRAM access and carefully manage limited WRAM. B. R-tree Spatial databases and GIS engines answer range-based queries, joins, and overlays on rectangles and polygons, which require indexing methods that can efficiently prune large portions of search space [9]–[13]. Introduced by Guttman [14], the R-tree is a height-balanced spatial index that organizes objects into a hierarchy of minimum bounding rectangles (MBRs). Leaf nodes store object MBRs, while internal nodes store MBRs that bound their children, enabling hierarchical pruning during query evaluation. Although node overlap can lead to multiple traversal paths, R-trees remain widely used in GIS, spatial databases, and scientific workloads due to their flexibility and effective support for spatial range queries. For static datasets, bulk-loading improves R-tree construction and query performance. One of the most widely adopted bulkloading algorithms is the Sort-Tile-Recursive (STR) method proposed by Leutenegger et al. [15]. STR builds a packed R-tree bottom-up by sorting objects along one dimension, partitioning them into slices, and grouping them into leaf nodes with fixed fanout; higher levels are formed recursively from child MBRs. STR achieves high space utilization and reduced overlap compared to incremental insertion, improving query pruning. In this work, we adopt STR bulk-loading due to its low overlap, high space utilization, and predictable levelwise structure, which are well suited for parallel spatial query processing. The parallel R-tree data structure has been well explored in the literature for multi-cores [16], GPUs [17]–[21] and distributed memory environments [22]–[25]. However, porting existing designs to the PIM system is not straightforward due to architectural differences between the traditional processorcentric and PIM paradigms. C. Prior Works: PIM-Friendly Indexes Most of the existing work on PIM focuses on data-parallel operators with regular access patterns, including table scans [3], [4], selection and aggregation [26], and hash-based joins [5]. Prior studies on commercial PIM platforms, particularly UPMEM, show that such operators benefit from high internal memory bandwidth and massive parallelism across DPUs [3], [5]. Similar trends have also been reported in earlier near-data processing systems targeting analytics workloads [26]–[28].
Indexing support on PIM has received comparatively less attention. Existing PIM-friendly index designs primarily target key–value workloads and rely on simplified data structures such as hashing or skip lists to avoid deep pointer traversal and irregular control flow, as exemplified by PIM-Tree [6]. More recently, Kim et al. proposed OLTPim, an end-to-end OLTP DBMS for commercial UPMEM systems that offloads pointerchasing components such as indexes and version chains to PIM, using hash-partitioned local B+trees and batched execution to amortize offload overheads [29]. A recent work has also explored space-partitioning indexes for multidimensional points on PIM, such as PIM-zd-tree [30], which leverages space-filling curve ideas to linearize multidimensional data and reduce traversal complexity. In contrast, R-trees perform hierarchical pruning over MBRs (bounding rectangles) and require multi-level traversal with data-dependent branching, which makes them structurally different from the above PIM index designs. Moreover, R-tree range queries are outputsensitive: query performance depends not only on the input size and traversal depth, but also on the number of overlapping objects produced as output, which is not known a priori. It presents additional implementation challenges to handle variable size output. The proposed design handles a variety of output sizes across different queries and since the memory allocation is different in PIM, our implementation takes care of output-sensitive nature of the data structure. To the best of our knowledge, we are not aware of any existing work that implements and evaluates R-tree range-query processing on commercial UPMEM PIM hardware; this work addresses this gap with a broadcast-based execution strategy that keeps host–DPU communication from dominating end-to-end execution. III. M ETHODOLOGY This section presents the three execution approaches considered in our study: a multi-threaded CPU implementation (CPU Baseline), a subtree-based PIM design used as the baseline (Baseline PIM R-tree), and the proposed broadcast-based PIM design (Broadcast PIM R-tree). A. Multi-threaded CPU Baseline We compare PIM-based execution against a multi-threaded CPU baseline that performs R-tree range queries entirely in host memory. To ensure a fair comparison, the CPU baseline uses the same R-tree structure as the proposed broadcast-based PIM approach, constructed on the host with identical bulkloading parameters. This ensures that performance differences arise from the execution model rather than from index structure. R-tree construction is performed sequentially, as it is a onetime preprocessing cost, while query processing is parallelized across CPU threads. Each query traverses the R-tree using bounding-box filtering followed by exact rectangle intersection tests, matching the semantics of the PIM kernel. We implement a custom multi-threaded search engine using POSIX threads, as publicly available R-tree libraries do not
Algorithm 1 Parallel CPU R-tree Range Query Processing (CPU Baseline) Require: R-tree root R, query set Q[0 . . . N − 1], threads T , chunk size C Ensure: Result array results[0 . . . N − 1] 1: Initialize shared atomic index idx ← 0 2: for all threads t = 0 to T − 1 in parallel do 3: while true do 4: start ← atomic fetch and add(idx, C) 5: if start ≥ N then break 6: end if 7: end ← min(start + C, N ) 8: for i = start to end − 1 do 9: results[i] ← S EARCH R- TREE(R, Q[i]) 10: end for 11: end while 12: end for 13: return results
provide scalable, thread-parallel query execution with explicit control over scheduling and traversal behavior. Parallel query processing uses dynamic, chunk-based scheduling to mitigate load imbalance caused by spatial skew and query selectivity. The R-tree is read-only during query execution, eliminating synchronization within the traversal. Algorithm 1 outlines the parallel CPU query processing strategy. B. Subtree-based Baseline PIM R-tree As a baseline, we implement a subtree-based PIM Rtree in which each DPU is assigned an independent R-tree subtree and processes queries locally. This design aligns with PIM systems, where DPUs operate on DPU-local MRAM address spaces without inter-DPU communication. We use this baseline to quantify the cost of subtree partitioning and host–DPU data movement. a) Fanout-Constrained R-tree Construction: To enforce a one-to-one mapping between subtrees and DPUs, we construct the R-tree on the host using a custom top-down bulkloading strategy that explicitly constrains the root fanout to the number of DPUs. Traditional R-tree constructions are not suitable for this as Guttman’s insertion-based R-tree yields data-dependent fanout, while STR bulk loading builds the tree bottom-up without controlling the number of top-level subtrees. Algorithm 2 outlines the construction, which recursively partitions rectangles using x- and y-center ordering to form spatially coherent groups while capping the root fanout. Although not a classical STR construction, this approach adopts STR-style spatial ordering to improve locality, reduce overlap, and balance subtree sizes. b) Subtree Serialization and Execution: Figure 2 illustrates the baseline workflow. After construction, the R-tree is partitioned at the root, and each level-1 subtree is serialized into a contiguous representation and transferred to its assigned DPU. Each DPU stores its subtree in MRAM and evaluates all queries locally using multiple tasklets.
Algorithm 2 Fanout-constrained R-tree creation in PIM Baseline Require: Rectangles R, number of DPUs P , leaf capacity B 1: function B UILD ( Rectangles R ) 2: if |R| ≤ B then return leaf node over R 3: end if 4: k ← min(P, ⌈|R|/B⌉) ▷ target number of children √ 5: Sort R by x-center and split into ⌈ k⌉ slabs 6: for all slabs do 7: Sort by y-center and partition into groups 8: Recursively build child nodes for each group 9: end for 10: return internal node with ≤ k children 11: end function 12: Build root T ← B UILD (R) and assign its children as one subtree per DPU
device-side pruning and MRAM-based leaf scans. In this heterogeneous system, the CPU orchestrates data distribution and query scheduling, and PIM hardware executes searches in parallel. Figure 3 shows the workflow.
Fig. 3: Workflow for Broadcast PIM R-tree range query processing on a heterogeneous CPU–PIM system.
Fig. 2: Three-step subtree-based PIM R-tree (PIM baseline) preparation: (1) top-down STR-inspired R-tree construction on the CPU, (2) partitioning at the root into level 1 subtrees, and (3) serialization of each subtree for DPU transfer.
In this Baseline PIM R-tree, query rectangles are broadcast to all DPUs in batches. Each DPU evaluates the complete query set independently against its locally stored subtree using T tasklets. Queries are statically partitioned across tasklets to eliminate synchronization overhead and avoid write contention during result accumulation. For each query, the DPU performs a recursive R-tree traversal starting from the root of its assigned subtree. At internal nodes, MBR intersection tests are applied to prune non-overlapping branches. At leaf nodes, all contained rectangles are examined for overlap with the query region, and the number of intersecting rectangles is counted. Each DPU produces a per-query overlap count corresponding to its subtree, and the host aggregates the partial counts returned by all DPUs to obtain the final query result. This design exposes parallelism across DPUs, but requires transferring a distinct serialized subtree to each DPU, leading to substantial host to DPU communication overhead. We use this subtree-based design as a PIM baseline to quantify the cost of per-DPU subtree transfers and motivate the broadcastbased execution strategy introduced next. C. Proposed Broadcast PIM R-tree We implement a heterogeneous CPU to PIM workflow in which the host constructs an R-tree, broadcasts a compact prefix of the index to all DPUs, partitions the leaf level across devices, and evaluates batched queries in parallel with
1) CPU-side R-tree construction: We construct the R-tree on the CPU using the standard bottom-up STR bulk-loading procedure, with fixed leaf and internal node capacities; the choice of parameters bounds the tree height but does not alter the STR grouping strategy. Let N denote the number of input rectangles. At the leaf level, rectangles are sorted by the midpoint of their horizontal p extent (xcenter = (xmin +xmax )/2) and partitioned into ⌈ N/B⌉ contiguous slices, where B is the leaf capacity (BUNDLEFACTOR). Within each slice, rectangles are sorted by the midpoint of their vertical extent (ycenter = (ymin + ymax )/2) and packed into leaf nodes of fixed capacity. Internal nodes are constructed recursively using the same STR grouping strategy: child nodes are treated as objects, sorted by the midpoint of their MBR extents, tiled into slices, and packed into parent nodes with fanout bounded by FANOUT. This process continues until a single root is formed. We select BUNDLEFACTOR and FANOUT such that the resulting R-tree has exactly three levels, with all leaves at level 2, as illustrated in Figure 4. This three-level design keeps the broadcast prefix (root + level-1) within DPU WRAM. Deeper trees would require broadcasting additional internal levels whose size can approach FANOUT, making WRAM a practical constraint. 2) BFS serialization on the host: To enable DPU execution, the entire R-tree is serialized into a flat array of nodes, replacing pointers with array indices. This is necessary because UPMEM DPUs do not support dynamic allocation or host pointers; all device memory must be statically allocated and index-addressable. Listing 1: SerializedNode (SN) structure used for breadth-first serialization. t y p e d e f s t r u c t SN { int isLeaf ; int count ; MBR mbr ;
Fig. 4: Three-level STR R-tree layout for a dataset of N rectangles. Each leaf node stores up to B rectangles, and internal nodes at level 1 have fanout F , where F equals the number of DPUs. The tree contains ⌈N/B⌉ leaf nodes and ⌈N/(B F )⌉ level 1 internal nodes.
int c h i l d r e n [MAX CHILDREN ] ; R e c t r e c t s [MAX RECTS ] ; } SN ; Here, MAX_CHILDREN equals the internal node fanout (FANOUT), and MAX_RECTS equals the leaf capacity (BUNDLEFACTOR). Serialization produces a contiguous array SN[0..K −1], where K is the total number of serialized nodes, laid out in breadth-first order. The root is stored at index 0, followed by all level 1 internal nodes and then all level 2 (leaf) nodes. With this layout, the beginning of the leaf level can be computed directly as 1 + SN[0].count, where SN[i].count denotes the number of children for internal node i (or the number of rectangles for a leaf node). Serialization is performed in a single breadth-first pass: the total node count K is computed in advance, memory is allocated once, and each node is written exactly once, yielding O(K) time complexity. Although depth-first layouts are common for traversal, our objective is efficient data placement and transfer. A breadth-first layout forms a compact prefix containing the shared upper levels, which can be broadcast once to all DPUs, while leaf nodes remain contiguous for coalesced per-DPU transfers. On UPMEM systems, broadcast transfers scale better with DPU count than repeated per-DPU copies; we exploit this property by broadcasting the shared upper levels only once [31]. 3) R-tree transfer to DPUs: R-tree transfer is carried out in two stages: (1) a one-time broadcast of the shared upper levels of the R-tree and (2) a parallel distribution of the remaining leaf nodes, which are local to individual DPUs. a) Broadcast of the upper levels: We broadcast the shared upper two levels once to all DPUs. Owing to breadthfirst serialization, the root and all level 1 internal nodes form a contiguous prefix SN[0..c], where c denotes the number of children of the root node. Since upper-level pruning requires only node metadata (isLeaf, count, and mbr), the host broadcasts a compact header representation instead of full nodes SN. This reduces host to DPU communication volume and initialization overhead while preserving correctness, as upper-level filtering relies solely on MBR–query intersection tests.
b) Parallel transfer of leaf nodes: The level 2 nodes (leaf) of the R-tree, are partitioned into contiguous slices and distributed across DPUs. Level 2 begins at index 1 + SN[0].count, and the slices are sized to balance the number of leaf nodes per DPU. Each slice is transferred using parallel, coalesced host to DPU transfers and stored in the DPU’s local MRAM. This data placement strategy balances workload across DPUs, eliminates inter-DPU communication, and enables fully independent parallel query execution. 4) Query broadcast and batching: Query rectangles are broadcast from the host to all DPUs in batches so that each query is evaluated against all leaf partitions. Broadcasting is required for correctness because each DPU stores only a disjoint subset of the leaf nodes, and a query may intersect leaves residing on multiple DPUs; partial results are therefore aggregated on the host. For each batch, the host broadcasts the batch size and the corresponding query rectangles, amortizing communication overhead and enabling reuse of the broadcasted upper-level metadata. 5) Parallel batch execution on DPUs: After receiving a query batch, each DPU processes the queries independently using multiple tasklets. Let F denote the number of DPUs and T the number of tasklets per DPU. Each DPU d ∈ {0, . . . , F − 1} stores a contiguous slice of the serialized R-tree leaf level in its local MRAM. We denote this slice by Ld ⊂ SN, where Ld consists exclusively of level 2 (leaf) nodes assigned to DPU d. At kernel launch, the broadcast upper-level metadata (root and level 1 nodes) is read from MRAM into WRAM using mram_read. This metadata is shared by all tasklets on the DPU. A barrier ensures that the WRAM-resident upperlevel data is available before query processing begins. Queries in the current batch are statically partitioned across tasklets to ensure load balance and to avoid synchronization or write contention. Each tasklet processes a disjoint subset of queries and operates independently. a) Two-phase query evaluation: For each assigned query, a tasklet performs a two-phase search. In Phase 1 (upper-level filtering), as shown in Algorithm 3 and Figure 5, the tasklet evaluates the query against a small, constant number (at most four) of level 1 MBRs. This bounded neighborhood ensures correctness near region boundaries. These MBRs are initially stored in MRAM and fetched once into WRAM. Because the upper levels contain only a small number of nodes, they fit easily within the DPU’s WRAM capacity and can be reused across all queries. The candidate level 1 nodes are determined by the DPU index and the root fanout, reducing the upperlevel filtering cost from O(c) to O(1), where c denotes the number of children of the root. If no overlap is detected at this stage, the query is discarded locally. In Phase 2 (local leaf scan), each tasklet sequentially scans the leaf nodes in Ld , where Ld denotes the subset of level 2 (leaf) nodes assigned to DPU d. The tasklet reads leaf data directly from MRAM and applies rectangle–query overlap tests. For each overlapping rectangle, a local counter is incremented. Because the leaf data are read-only during this phase, the scan is performed without buffering rectangles in
Algorithm 3 Parallel Batch Execution on each DPU Require: Upper-level headers in MRAM Hdr[0..c], c children, local leaf slice Ld , query batch Qb , tasklets T Ensure: Per-query overlap counts stored in variable DPU_OVERLAP_COUNT 1: Tasklet 0: Read Hdr[0..c] from MRAM into WRAM 2: Barrier synchronization 3: Partition queries in Qb evenly across tasklets 4: for each tasklet t in parallel do 5: for each assigned query q do 6: Phase 1: Test overlap with at most four level 1 MBRs (WRAM) 7: if overlap detected then 8: Phase 2: Scan leaf nodes in Ld (MRAM) and count overlaps 9: else 10: Set overlap count to 0 11: end if 12: end for 13: end for 14: Reduce per-tasklet cycle counts to obtain per-DPU kernel time
WRAM. Per-query overlap counts are accumulated in WRAM and written back to MRAM upon completion. Tasklets execute independently without inter-tasklet communication. Kernel execution time on a DPU is defined as the maximum execution time across its tasklets, since tasklets execute concurrently and overall completion is determined by the slowest tasklet. This per-DPU kernel time is used as the batch execution time in our analysis.
Fig. 5: DPU-index–guided upper-level filtering in Broadcast PIM R-tree. DPUs are mapped to level 1 regions based on their index. Each DPU evaluates overlap against only a small neighborhood of adjacent level 1 MBRs (highlighted), reducing upper-level filtering from O(c) to O(1) per query. IV. I MPLEMENTATION We implement both the Baseline PIM R-tree and the proposed Broadcast PIM R-tree on a commercial UPMEM system. The host-side code is written in C and uses the UPMEM SDK to manage DPU allocation, data movement, and kernel execution, while DPU kernels are implemented in C and
execute directly on the DPUs. The implementation follows a host–device execution model in which the CPU performs index construction and orchestration, and DPUs execute parallel spatial query processing within memory. A. Host-side implementation The host is responsible for R-tree construction, serialization, query preparation, and result aggregation. For both methods, the R-tree is constructed on the CPU using bulk-loading and serialized into a contiguous, index-addressable representation suitable for DPU execution. For the subtree-based baseline, the host partitions the R-tree at the root into disjoint subtrees, serializes each subtree independently, and transfers one serialized subtree to each DPU. Query rectangles are broadcast in batches, and each DPU processes all queries against its local subtree. For the Broadcast PIM R-tree method, the host serializes the entire R-tree in breadth-first order and separates it into two parts: (i) a shared prefix consisting of the root and level 1 internal nodes, and (ii) the level 2 leaf nodes. The shared prefix is broadcast once to all DPUs using dpu_broadcast_to, while the leaf nodes are partitioned into contiguous slices and transferred to DPUs using parallel, coalesced host-toDPU transfers. Query rectangles are broadcast to all DPUs in batches. After kernel execution, per-query overlap counts are retrieved from DPUs and aggregated on the host. B. DPU-side implementation Each DPU stores its assigned tree data and query batches in MRAM. Query processing is parallelized across multiple tasklets within each DPU. Upon kernel launch, a designated tasklet initializes shared state, fetches any required upperlevel metadata from MRAM into WRAM, and configures the hardware performance counter. A barrier ensures that all tasklets begin query processing with a consistent view of shared data. In the subtree-based baseline, each DPU traverses its local serialized subtree recursively for every query, applying MBR pruning at internal nodes and scanning leaf rectangles to count overlaps. In the Broadcast PIM R-tree, each DPU processes only its assigned slice of leaf nodes. For each query, tasklets perform a two-phase evaluation: a lightweight upper-level filtering phase using WRAM-resident metadata, followed by a local leaf scan directly from MRAM when filtering succeeds. Queries are statically partitioned across tasklets to ensure load balance and to avoid synchronization or write contention. Tasklets operate independently and do not communicate during execution. C. Performance measurement Each tasklet records its execution cycles using the DPU hardware performance counter and stores the value in the DPU_PERF structure. For each DPU, the kernel execution time is defined as the maximum cycle count across its tasklets, reflecting the completion time of parallel execution. Host–DPU transfer times and end-to-end execution times are measured using host-side timers and are reported separately in the evaluation.
a) Energy measurement: Energy consumption is measured using an external PN150 power meter connected to the UPMEM server power supply. Power is sampled during execution of the CPU-only and DPU-accelerated phases and combined with the corresponding execution time to compute energy consumption. These measurements are synchronized with kernel execution and host–DPU transfers. Detailed power states, datasets, and energy-efficiency results are reported in Section V-G. V. E XPERIMENTAL E VALUATION This section evaluates the performance, scalability, and energy efficiency of our Broadcast PIM R-tree and contrasts it with both a multi-threaded CPU Baseline and a Baseline PIM R-tree. Our evaluation is structured to examine three aspects of PIM-based spatial query processing: (i) when PIM execution outperforms CPU-based approaches, (ii) how broadcast-based execution compares to subtree partitioning (Baseline PIM Rtree) in terms of communication efficiency and scalability, and, (iii) how memory access patterns influence performance and energy behavior on commercial PIM hardware. We first describe the experimental setup, datasets, and timing methodology, and then present detailed performance and energy results across a range of workloads. A. Experimental Setup We evaluate our experiments on two systems: M ILL and UPMEM-PIM. CPU baselines are measured on a shared university-operated HPC cluster named M ILL with dual-socket Intel Xeon Gold 6248 processors (20 cores per socket, 40 cores total) running at a base frequency of 2.50 GHz. CPU experiments use 8 threads for parallel execution and a single thread for sequential baselines. The thread count is chosen to represent a moderate level of parallelism and to avoid memory bandwidth saturation. All CPU runs use the same Rtree structure and query semantics as the PIM implementation to ensure comparability. PIM experiments are conducted on a commercial UPMEM system with up to 2,540 DPUs running at 400 MHz with 11 tasklets (out of 16) per DPU, where the host CPU shares memory channels with PIM DIMMs. Although the platform nominally supports 2,560 DPUs (20 DIMMs), allocations beyond 2,540 DPUs fail with a dpu allocation error, so we use 2,540 DPUs as the maximum stable configuration. We use 11 tasklets since performance saturates beyond 11. DPUs execute independently without inter-DPU communication. Queries are processed in batches of up to 10,000, and partial results are aggregated on the host. We note that CPU performance on M ILL represents an optimistic CPU-only baseline without PIM-induced memory bandwidth contention, while CPU execution on UPMEM reflects a system-level comparison where the host shares memory channels with PIM DIMMs. These two provide complementary perspectives for evaluating PIM performance. a) Datasets: We evaluate our approach using both realworld and synthetic spatial datasets that span a wide range of
TABLE I: Summary of datasets and query workloads. Dataset Sports (UCR-STAR) Lakes (UCR-STAR) Synthetic (SPIDER)
Dataset Size (#MBRs) 999K 8.4M 16M
Query Sizes (#Queries) 9K (1%), 49K (5%) 99K (10%), 249K (25%) 84K (1%), 420K (5%) 841K (10%), 2.1M (25%) 159K (1%), 798K (5%) 1.6M (10%), 3.99M (25%)
sizes, spatial distributions, and memory behaviors. The realworld datasets are drawn from UCR-STAR [32], while the synthetic dataset is generated using SPIDER [33]. All datasets consist of rectangles represented as (xmin , ymin , xmax , ymax ). To support execution on UPMEM PIM hardware, which does not efficiently support floating-point operations, all coordinates are converted to 32-bit integers using a fixed-precision scaling scheme. Together, these datasets allow us to study workloads that are cache-friendly (small datasets), moderately memoryintensive, and heavily memory-bound. For each dataset, we vary the number of range queries from approximately 1% to 25% of the whole dataset, enabling us to evaluate both low and high query pressure regimes. Table I summarizes the datasets used in our experiments. b) Timing Methodology: We measure CPU-seqM ILL and CPU-parM ILL as end-to-end wall-clock execution time on M ILL. These measurements include the complete CPU queryprocessing pipeline, covering query input handling, R-tree traversal, overlap testing, and result aggregation. CPU-seqM ILL corresponds to single-threaded execution, while CPU-parM ILL corresponds to multi-threaded execution using 8 CPU threads. On UPMEM-PIM, we separately measure kernel execution time and end-to-end execution time. K ERNEL UPMEM-PIM measures the DPU kernel execution time only and is obtained using the DPU hardware cycle counter, taking the maximum cycle count across tasklets to represent kernel completion. E2E UPMEM-PIM measures the full end-to-end execution time on UPMEM-PIM, including host to DPU data transfers, DPU kernel execution, and host-side result aggregation. B. Comparison with CPU Baseline Host execution on a PIM-equipped system is constrained by reduced host memory bandwidth because part of the memory bandwidth is used by the PIM DIMMs [34]. To ensure a fair evaluation, we report two baselines. The first is CPU Baseline measured on M ILL, which uses only host DRAM and provides an optimistic reference without PIMinduced bandwidth contention. The second is measured on the UPMEM-PIM, where the CPU shares memory channels with PIM DIMMs, enabling a direct system-level comparison with PIM end-to-end execution. Table II compares the execution time and speedup of the proposed Broadcast PIM R-tree against CPU Baseline across three datasets and varying query selectivities. We report (i) sequential and parallel CPU execution on the M ILL, (ii) DPU kernel time K ERNEL UPMEM-PIM and total DPU time, E2E UPMEM-PIM on the UPMEM-PIM, and (iii) PIM’s
TABLE II: Broadcast PIM R-tree execution on UPMEMPIM versus parallel CPU Baseline on M ILL. Cross-platform speedups report PIM kernel and end-to-end performance relative to CPU parallel execution on M ILL. Query
M ILL
UPMEM-PIM
Cross-platform Speedup
CPU Seq
CPU Kernel Par
PIM E2E Kernel
PIM E2E
0.42 2.16 4.22 10.42
0.45 0.45 0.91 1.80
1.10 2.77 4.85 11.07
1.50 0.30 0.30 0.24
0.41 0.16 0.19 0.16
Sports
1% 5% 10% 25%
0.30 1.50 3.00 7.52
Lakes
1% 15.32 2.59 5% 74.38 10.98 10% 150.74 20.69 25% 361.71 49.80
3.61 6.00 17.57 23.85 35.92 46.93 87.73 112.90
0.72 0.62 0.58 0.57
0.43 0.46 0.44 0.44
Synthetic
1% 18.65 2.58 5% 93.63 12.81 10% 187.07 25.49 25% 469.97 64.47
1.55 7.76 15.54 39.03
1.66 1.65 1.64 1.65
0.49 0.73 0.78 0.81
5.31 17.49 32.78 79.26
speedups relative to the parallel CPU Baseline. The results show Broadcast PIM R-tree achieves up to 1.66× kernel speedup vs. CPU Baseline on the Synthetic dataset, but does not outperform on the real datasets in this configuration. This behavior is consistent with prior PIM studies, where optimized multi-threaded CPU implementations often remain competitive or superior for complex data structures. Nevertheless, the observed kernel-level speedups on the Synthetic workload indicate that, when memory-level parallelism is effectively exploited and access patterns are well balanced, PIM execution can exceed CPU-parallel performance. These results highlight the potential of broadcast-based inmemory filtering and motivate further optimization of data placement, query batching, and communication overheads to close the gap for real-world workloads. While CPU parallelization on M ILL achieves up to 7× speedup over sequential execution, performance improvements diminish as query volume increases at the evaluated thread count. This behavior suggests that query processing becomes increasingly constrained by shared-memory bandwidth and cache contention rather than compute capacity. Figure 6 highlights the fundamental difference between CPU and PIM execution: CPU performance is limited by a shared-memory subsystem, whereas PIM execution distributes memory accesses across independent DPUs. As a result, PIM benefits from memory-intensive workloads, achieving kernel speedups of up to 15× on the Synthetic dataset, where query processing is dominated by irregular memory accesses. Here, CPU speedup is computed relative to CPU sequential execution on M ILL, and PIM kernel speedup is computed relative to sequential CPU phase execution on UPMEM-PIM. C. Comparison of Broadcast PIM R-tree and Baseline PIM R-tree Execution Table III, which reports results measured entirely on the UPMEM-PIM, shows that the Broadcast PIM R-tree con-
15.0
CPU Speedup (8 Threads) PIM Kernel Speedup
12 10 Speedup
Data set
14
8 6
7.3
7.2 5.8 3.6
4 2 0
1.3 Sports
Lakes Dataset
Synthetic
Fig. 6: Comparison of CPU-parallel speedup on M ILL and PIM kernel speedup on UPMEM-PIM across datasets. CPU speedup plateaus at approximately 6–7×, while PIM kernel speedup increases substantially with dataset size. Here, CPU speedup is relative to CPU sequential execution on MILL, while PIM kernel speedup is relative to CPU sequential execution on UPMEM-PIM.
Fig. 7: Kernel and communication time breakdown for the Lakes dataset (8.4M rectangles) for both Broadcast-based method and Subtree-based method on UPMEM-PIM.
sistently outperforms the subtree-based baseline across all datasets and query sizes. While both approaches achieve comparable kernel speedups, the subtree-based design suffers from substantially higher end-to-end execution time due to excessive host to DPU communication. This effect is particularly pronounced for the Lakes dataset, where Broadcast PIM R-tree execution achieves end-to-end speedups of up to 2.83×, compared to less than 0.5× for the Baseline PIM Rtree approach. Figure 7 explains this behavior by breaking down kernel and communication time for the Lakes dataset. We observe similar performance on the other datasets, so we omit those results. The subtree-based method is clearly communication dominated: communication time exceeds kernel execution time at all query sizes and grows rapidly with increasing query volume due to repeated subtree transfers and per-DPU data movement. In contrast, the broadcast-based approach significantly reduces communication overhead by broadcasting the upper R-tree levels once and reusing them across all queries, resulting in a
4.0
End-to-End Speedup (Host_Time/Total_DPU_Time) Kernel-only Speedup (Host_Time/Kernel_Time)
Speedup (×)
3.5
3.66×
3.0
2.95×
2.5
2.35×
2.70×
2.0 1.5 1.0
1.12× 0.67×
0.5 0.60× 0.0 500
1.04× 750
1000
1250
1500
1750
Number of DPUs
2000
2250
2500
Fig. 8: Strong scaling of broadcast based PIM R-tree search on fixed dataset (8.4M rectangles). Kernel-only and end-to-end speedups improve significantly as more DPUs participate.
more balanced execution profile where kernel time becomes the dominant cost. Together, these results demonstrate that the broadcast-based design effectively mitigates the communication bottleneck inherent in subtree-based PIM R-trees, enabling better scalability and higher end-to-end performance. The observed performance trends vary across datasets due to differences in dataset size and memory behavior. The Sports dataset exhibits limited benefit from PIM execution because its smaller working set provides insufficient parallel work to amortize host–DPU overheads. The Lakes dataset represents an intermediate case, where larger data volume and reduced cache effectiveness allow the broadcast-based design to mitigate communication costs and achieve consistent end-to-end speedups. In contrast, the Synthetic dataset exhibits highly irregular and memory-dominated access patterns, maximizing DPU utilization and allowing PIM execution to achieve the largest performance gains. Overall, these results show that minimizing communication is critical for scalable PIM-based spatial query processing. D. Strong Scaling To evaluate scalability with fixed problem size, we keep both the dataset (8.4M rectangles) and the query set (420,967 rectangles) fixed, while increasing the number of DPUs from 512 to 2,540. Figure 8 shows that both kernel-only (H OSTS EQ UPMEM-PIM /K ERNEL UPMEM-PIM ) and end-to-end speedups (H OST-S EQ UPMEM-PIM /E2E UPMEM-PIM ) improve steadily as the number of DPUs increases, demonstrating effective strong scaling of the broadcast-based PIM R-tree. Kernel speedup grows more rapidly than end-to-end speedup, reflecting the increasing impact of fixed host to DPU communication overheads at higher DPU counts, while overall results indicate that the proposed design effectively exploits additional DPU parallelism for a fixed problem size. In addition to scaling across DPUs, we evaluate intra-DPU strong scaling by varying the number of tasklets per DPU. Figure 9 shows kernel and end-to-end speedup as a function of tasklet count for the Lakes and Synthetic datasets. Speedup saturates beyond 8–11 tasklets, indicating MRAM bandwidth contention limits intra-DPU scalability.
Fig. 9: Effect of tasklet parallelism on PIM performance. Kernel and end-to-end speedups are shown for the Lakes and Synthetic datasets as the number of tasklets per DPU increases.
Fig. 10: Average per-batch timing: host-to-DPU transfer, DPU kernel execution, and result retrieval of Lake dataset in UPMEM-PIM.
E. Batchwise Timing Breakdown To understand the runtime behavior of the PIM execution pipeline, we measure the per-batch latency of (i) query transfer, (ii) kernel execution time from cycle-accurate DPU counters, and, (iii) result retrieval. Figure 10 shows the average time of these steps across all batches for Lakes dataset. It clearly shows that for our proposed Broadcast-based method, communication is not dominant. F. Memory-Centric Performance Analysis R-tree range query processing on PIM is dominated by memory access rather than arithmetic computation. To characterize this behavior, we collect lightweight DPU-side counters that track node visits, rectangle tests, and MRAM traffic during kernel execution. These measurements provide insight into the memory access patterns that largely determine DPU kernel performance. During execution, each DPU traverses its assigned leaf slice using bounding-box filtering followed by per-rectangle intersection tests. As a result, MRAM traffic is primarily generated by reading node metadata and streaming leaf rectangles, while MRAM writes are limited to per-query result counts. Table IV summarizes the aggregate memoryaccess statistics for the largest real workload (8.4M rectangles, 420,967 queries, 2,540 DPUs). Across all DPUs, the kernel reads approximately 539 GB from MRAM and writes 8 GB, with more than 5.2 billion rectangle intersection tests performed.
TABLE III: Performance comparison of Broadcast PIM R-tree and Baseline PIM R-tree entirely run on UPMEM-PIM with DPU: 2540, tasklets: 11. Dataset
Sports
Lakes
Synthetic
Query Size 9,998 49,986 99,971 249,928 84,194 420,967 841,932 2,104,829 159,328 798,037 1,597,493 3,998,921
Host (s) 0.41 2.00 3.99 9.95 12.95 64.35 130.12 319.57 23.52 117.75 236.19 594.22
Broadcast PIM R-tree Kernel Total Kernel (s) DPU Speedup 0.30 1.10 1.35 1.50 2.77 1.34 3.00 4.85 1.33 7.52 11.07 1.32 3.61 6.00 3.59 17.57 23.85 3.66 35.92 46.93 3.62 87.72 112.90 3.64 1.55 5.31 15.17 7.76 17.49 15.18 15.54 32.78 15.20 39.03 79.26 15.23
TABLE IV: Aggregate MRAM access profile of the DPU kernel. Metric Total MRAM bytes read Total MRAM bytes written Total MRAM traffic Nodes visited Rectangles tested Kernel execution time Attained aggregate MRAM bandwidth
Value 538,851 MB 8,157 MB 547,009 MB 19.3 billion 5.28 billion 23.48 s
End-to-End Speedup 0.37 0.72 0.82 0.90 2.16 2.70 2.77 2.83 4.43 6.73 7.21 7.50
G. Energy Efficiency Analysis We evaluate energy efficiency by measuring active system power and execution time separately for the CPU search phase and the DPU kernel phase in UPMEM-PIM. Background power states are measured only to characterize baseline system consumption and are not included in the energy calculations. Specifically, the system draws 14.5 W in standby (server off), approximately 433 W in idle (no application running), and 528–530 W in interactive idle (SSH session active). For CPU-only execution, energy is computed using the active power measured while the CPU performs overlap checking, multiplied by the CPU search time. For PIM execution, energy is computed using the active power measured during DPU kernel execution (i.e., while query batches are executing
Baseline PIM R-tree Kernel Total Kernel (s) DPU Speedup 0.33 2.25 0.82 1.64 7.20 0.80 3.28 13.38 0.80 8.21 32.02 0.80 4.13 13.22 1.44 20.61 62.38 1.44 41.24 119.88 1.43 103.19 304.23 1.44 0.65 18.20 26.51 3.25 90.78 26.57 6.54 167.20 26.58 16.33 395.04 26.55
End-to-End Speedup 0.12 0.18 0.20 0.21 0.45 0.48 0.49 0.49 0.95 0.95 1.04 1.10
TABLE V: Energy comparison between CPU search phase and the DPU kernel phase in UPMEM-PIM. Energy efficiency is computed as the ratio of CPU energy to DPU energy. The same execution phases and values are also reported in Table III. Dataset
Query Size
Runtime (s) CPU DPU
Energy (kJ) CPU DPU
Sports
1% 5% 10% 25%
0.41 2.00 3.99 9.95
0.23 1.14 2.27 5.66
Lakes
1% 5% 10% 25%
24.4 GB/s
The measured aggregate bandwidth of 24.4 GB/s indicates that DPU kernel execution time closely tracks the volume of MRAM accesses rather than compute throughput. Although this bandwidth does not saturate the peak capacity of the UPMEM system, it reflects the memory-dominated nature of R-tree traversal, where each rectangle test performs only a small number of integer comparisons. As subtree size and rectangle density increase, kernel runtime scales proportionally with MRAM access volume, while host to DPU communication remains a secondary contributor to end-to-end time. These results indicate that PIM execution benefits spatial range queries primarily by minimizing data movement through neardata execution within DRAM, rather than by saturating the peak memory bandwidth of the UPMEM system.
Host (s) 0.27 1.31 2.62 6.57 5.93 29.64 58.89 148.98 17.23 86.34 173.81 433.56
1% 5% Synthetic 10% 25%
0.30 1.50 3.00 7.52
Energy Efficiency
0.18 0.89 1.79 4.48
1.28 1.28 1.27 1.26
12.95 3.61 64.35 17.57 130.12 35.92 319.57 87.72
7.37 2.15 36.62 10.47 74.04 21.41 179.36 51.76
3.43 3.50 3.46 3.51
23.52 117.75 236.19 594.22
13.38 67.00 134.39 338.11
14.54 14.50 14.51 14.54
1.55 7.76 15.54 39.03
0.92 4.62 9.26 23.26
on the DPUs), multiplied by the kernel execution time. During the CPU phase, active system power ranges from 567–571 W, whereas during DPU kernel execution it increases modestly to 590–601 W. Although DPU execution draws slightly higher instantaneous power, its substantially shorter kernel runtime results in significantly lower total energy consumption. Table V reports runtime and energy consumption for CPUonly and PIM-accelerated execution across three datasets. For the Sports dataset, energy savings are modest (about 1.26– 1.28×), as the dataset fits well in CPU caches and CPU execution already benefits from high locality. In contrast, for the Lakes dataset, PIM execution consistently achieves a stable energy reduction of approximately 3.4–3.5× across all query sizes. The Synthetic dataset shows the largest gains, exceeding 14× energy efficiency across all query sizes. This reflects its highly memory-intensive access pattern, where CPU execution suffers from poor cache reuse, while PIM benefits from neardata processing and parallel MRAM access. Overall, Table V demonstrates that energy efficiency improves with dataset size and memory intensity, highlighting the advantage of PIM
architectures for large-scale, memory-bound spatial workloads. VI. C ONCLUSION AND F UTURE W ORK This work demonstrates the first implementation of hierarchical R-tree range queries onto a commercial PIM system. We introduce a broadcast-based execution strategy that exploits the filtering semantics of R-trees by broadcasting upper levels to all DPUs and distributing lower-level subtrees for parallel batched execution. Compared to a subtree-based PIM baseline, this design avoids per-DPU subtree transfers and prevents host–DPU communication from dominating execution, enabling scalable query processing on UPMEM hardware. Experimental results on real and synthetic datasets using up to 2,540 DPUs show that the proposed approach delivers consistent kernel and end-to-end speedups over an optimized CPU R-tree baseline while significantly improving energy efficiency. In the Lakes dataset, strong scaling reduces kernel time by up to 3.66× and achieves a 2.70× end-to-end speedup, while consuming approximately 3.4× less energy than CPU execution in the PIM server. These results highlight the importance of communication-aware index design and execution to enable efficient and energy-efficient spatial query processing on PIM architectures. While broadcast-based execution is most effective for large, memory-intensive workloads, performance gains are limited for small or cache-efficient datasets where communication overheads cannot be fully amortized. Based on this observation, we identify two promising directions for future work. First, we plan to explore the use of multiple DPU sets to overlap computation with data transfers, which is especially important for workloads with limited per-query computation. Second, we aim to develop an analytical performance model for PIM-based spatial queries that captures computation, communication, and memory-access costs, enabling principled decisions about when PIM execution is preferable to multicore CPU processing. ACKNOWLEDGMENTS This material is based on work supported by the National Science Foundation under Grants No. 2344578, No. 2402987 and No. 2402988. R EFERENCES [1] W. A. Wulf and S. A. McKee, “Hitting the memory wall: Implications of the obvious,” ACM SIGARCH computer architecture news, vol. 23, no. 1, pp. 20–24, 1995. [2] UPMEM, “Introduction to UPMEM PIM: Processing-in-Memory (PIM) on DRAM Accelerator (White Paper).” White paper, UPMEM, Grenoble, France, 2018. [3] J. Gómez-Luna, I. El Hajj, I. Fernandez, C. Giannoula, G. F. Oliveira, and O. Mutlu, “Benchmarking a new paradigm: Experimental analysis and characterization of a real processing-in-memory system,” IEEE Access, vol. 10, pp. 52565–52608, 2022. [4] A. Baumstark, M. A. Jibril, and K.-U. Sattler, “Accelerating large table scan using processing-in-memory technology,” Datenbank-Spektrum, vol. 23, no. 3, pp. 199–209, 2023. [5] C. Lim, S. Lee, J. Choi, J. Lee, S. Park, H. Kim, J. Lee, and Y. Kim, “Design and analysis of a processing-in-dimm join algorithm: A case study with upmem dimms,” Proceedings of the ACM on Management of Data, vol. 1, no. 2, pp. 1–27, 2023.
[6] H. Kang, Y. Zhao, G. E. Blelloch, L. Dhulipala, Y. Gu, C. McGuffey, and P. B. Gibbons, “Pim-trie: A skew-resistant trie for processing-inmemory,” in Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 1–14, 2023. [7] D. Patterson, T. Anderson, N. Cardwell, R. Fromm, K. Keeton, C. Kozyrakis, R. Thomas, and K. Yelick, “A case for intelligent RAM,” IEEE micro, vol. 17, no. 2, pp. 34–44, 2002. [8] F. Devaux, “The true processing in memory accelerator,” in Proceedings of the IEEE Hot Chips 31 Symposium (HCS), pp. 1–24, IEEE Computer Society, 2019. [9] S. Puri, D. Agarwal, X. He, and S. K. Prasad, “MapReduce algorithms for GIS polygonal overlay processing,” in 2013 IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum, pp. 1009–1016, IEEE, 2013. [10] D. Aghajarian, S. Puri, and S. Prasad, “GCMF: an efficient end-to-end spatial join system over large polygonal datasets on GPGPU platform,” in Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’16, (New York, NY, USA), Association for Computing Machinery, 2016. [11] S. Puri and S. K. Prasad, “A Parallel Algorithm for Clipping Polygons with Improved Bounds and a Distributed Overlay Processing System Using MPI,” in 2015 15th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing, pp. 576–585, 2015. [12] J. Yang, S. Puri, and H. Zhou, “Fine-grained dynamic load balancing in spatial join by work stealing on distributed memory,” in Proceedings of the 30th International Conference on Advances in Geographic Information Systems, SIGSPATIAL ’22, (New York, NY, USA), Association for Computing Machinery, 2022. [13] Y. Liu, J. Yang, and S. Puri, “Hierarchical Filter and Refinement System Over Large Polygonal Datasets on CPU-GPU,” in 2019 IEEE 26th International Conference on High Performance Computing, Data, and Analytics (HiPC), pp. 141–151, 2019. [14] A. Guttman, “R-trees: A dynamic index structure for spatial searching,” in Proceedings of the 1984 ACM SIGMOD international conference on Management of data, pp. 47–57, 1984. [15] S. T. Leutenegger, M. A. Lopez, and J. Edgington, “STR: A simple and efficient algorithm for R-tree packing,” in Proceedings 13th international conference on data engineering, pp. 497–506, IEEE, 1997. [16] I. Kamel and C. Faloutsos, “Parallel R-trees,” ACM SIGMOD Record, vol. 21, no. 2, pp. 195–204, 1992. [17] B. Yu, H. Kim, W. Choi, and D. Kwon, “Parallel Range Query Processing on R-Tree with Graphics Processing Unit,” in 2011 IEEE Ninth International Conference on Dependable, Autonomic and Secure Computing, pp. 1235–1242, 2011. [18] S. K. Prasad, M. McDermott, X. He, and S. Puri, “GPU-based Parallel R-tree Construction and Querying,” in 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, pp. 618–627, IEEE, 2015. [19] J. Kim, S.-G. Kim, and B. Nam, “Parallel multi-dimensional range query processing with R-trees on GPU,” Journal of Parallel and Distributed Computing, vol. 73, no. 8, pp. 1195–1207, 2013. [20] S. You, J. Zhang, and L. Gruenwald, “Parallel spatial query processing on gpus using R-trees,” in Proceedings of the 2nd ACM SIGSPATIAL international workshop on analytics for big geospatial data, pp. 23–31, 2013. [21] L. Geng, R. Lee, and X. Zhang, “LibRTS: A Spatial Indexing Library by Ray Tracing,” in Proceedings of the 30th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, PPoPP ’25, (New York, NY, USA), p. 396–411, Association for Computing Machinery, 2025. [22] B. Schnitzer and S. T. Leutenegger, “Master-client R-trees: A new parallel R-tree architecture,” in Proceedings. Eleventh International Conference on Scientific and Statistical Database Management, pp. 68– 77, IEEE, 1999. [23] L. Shuhua, Z. Fenghua, and S. Yongqiang, “A Design of Parallel R-tree on Cluster of Workstations,” in International Workshop on Databases in Networked Information Systems, pp. 119–133, Springer, 2000. [24] M. Xiao, H. Wang, L. Geng, R. Lee, and X. Zhang, “Catfish: Adaptive RDMA-enabled R-Tree for Low Latency and High Throughput,” in 2019 IEEE 39th International Conference on Distributed Computing Systems (ICDCS), pp. 164–175, 2019. [25] M. Xiao, H. Wang, L. Geng, R. Lee, and X. Zhang, “An RDMA-enabled In-memory Computing Platform for R-tree on Clusters,” ACM Trans. Spatial Algorithms Syst., vol. 8, Feb. 2022.
[26] J. Ahn, S. Yoo, O. Mutlu, and K. Choi, “PIM-enabled instructions: A low-overhead, locality-aware processing-in-memory architecture,” ACM SIGARCH Computer Architecture News, vol. 43, no. 3S, pp. 336–348, 2015. [27] R. Balasubramonian, J. Chang, T. Manning, J. H. Moreno, R. Murphy, R. Nair, and S. Swanson, “Near-data processing: Insights from a micro46 workshop,” IEEE Micro, vol. 34, no. 4, pp. 36–42, 2014. [28] V. Seshadri, D. Lee, T. Mullins, H. Hassan, A. Boroumand, J. Kim, M. A. Kozuch, O. Mutlu, P. B. Gibbons, and T. C. Mowry, “Ambit: In-memory accelerator for bulk bitwise operations using commodity DRAM technology,” in Proceedings of the 50th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 273–287, 2017. [29] H. Kim, Y. Zhao, A. Pavlo, and P. B. Gibbons, “No cap, this memory slaps: Breaking through the memory wall of transactional database systems with processing-in-memory,” Proceedings of the VLDB Endowment, vol. 18, no. 11, pp. 4241–4254, 2025. [30] Y. Zhao, H. Kang, Z. Men, Y. Gu, G. E. Blelloch, L. Dhulipala, C. McGuffey, and P. B. Gibbons, “Pim-zd-tree: A fast space-partitioning index leveraging processing-in-memory,” in Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming, pp. 480–495, 2026. [31] S. Cai, B. Tian, H. Zhang, and M. Gao, “Pimpam: Efficient graph pattern matching on real processing-in-memory hardware,” Proceedings of the ACM on Management of Data, vol. 2, no. 3, pp. 1–25, 2024. [32] S. Ghosh, T. Vu, M. A. Eskandari, and A. Eldawy, “UCR-STAR: The UCR spatio-temporal active repository,” SIGSPATIAL Special, vol. 11, no. 2, pp. 34–40, 2019. [33] P. Katiyar, T. Wu, S. Migliorini, A. Belussi, and A. Eldawy, “Spiderweb: A spatial data generator for big spatial data applications.” https://spider. cs.ucr.edu/, 2021. [34] B. Friesel, M. Lütke Dreimann, and O. Spinczyk, “A full-system perspective on upmem performance,” in Proceedings of the 1st Workshop on Disruptive Memory Systems, pp. 1–7, 2023.