Theoretical Analysis of Batch-Dynamic kd-trees for Processing-in-Memory Architectures

Many applications that operate on high-dimensional data rely on the kd-tree, a space-partitioning index that offers logarithmic complexity for most queries and updates. As dataset sizes scale, however, performance degrades due to the memory wall: data movement between CPU and main memory becomes the dominant cost, effectively reducing efficiency toward linear time. This work explores a processing-in-memory (PIM) approach that offloads key kd-tree operations to computational units embedded within memory. By exploiting near-data processing, the proposed design minimizes off-chip communication and reduces latency, enabling more efficient traversal and updates. The proposed kd-tree model supports batch-parallel queries and dynamic updates. The design enables efficient execution of k-nearest neighbors (kNN) and range queries, which are central to data processing clusters and density-based algorithms such as DBSCAN. An additional core idea is a tunable structure that, through practical design choices, enables a fine control over the trade-off between communication overhead, memory overhead and query batch size.