Parallel Prefix Filter Search for Weighted Jaccard Similarity

Abstract

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.