Similarity search over high-dimensional sparse feature vectors is a fundamental problem in applications such as information retrieval, data mining, and machine learning. In this paper, we present PreFast, a scalable parallel prefix-filtering framework for top-k similarity search over non-negative weighted feature vectors. We design and implement multiple parallel variants of the prefix-filter to leverage modern computing architectures. First, we introduce a shared-memory (multi-threaded) implementation that exploits fine-grained parallelism during prefix traversal and candidate verification. Second, we extend the algorithm to an MPI-based distributed-memory setting by integrating a novel coordinated early termination strategy. Our MPI-based design enables scalable query processing across multiple compute nodes. Third, we develop a GPU-accelerated implementation that offloads candidate evaluation and similarity computation to massively parallel CUDA kernels. Across these implementations, we incorporate efficient top-k maintenance and early termination mechanisms, allowing a substantial reduction in unnecessary computations. For evaluation, we used geospatial feature vectors extracted from OpenStreetMap polygonal data to answer weighted Jaccard-based shape similarity queries. Experimental results show that PreFast achieves up to 22 × speedup over the sequential baseline on the distributed implementation and up to 26 × speedup on a single GPU, while maintaining over \(99\%\) recall compared to the exact similarity search.
S. Pokharel, A. Subedi, Elizabeth Oluwadamilola Durowoju et al.· 0 citations
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.
Tasmia Jannat, Michael Gowanlock, S. Puri· IEEE International Symposium...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
