PL2AP: Fast Parallel Cosine Similarity Search

David C. Anastasiu and George Karypis
5th Workshop on Irregular applications: Architectures and Algorithms, Supercomputing, 2015
Download Paper
Solving the AllPairs similarity search problem entails finding all pairs of vectors in a high dimensional sparse dataset that have a similarity value higher than a given threshold. The output form this problem is a crucial component in many real-world applications, such as clustering, online advertising, recommender systems, near-duplicate document detection, and query refinement. A number of serial algorithms have been proposed that solve the problem by pruning many of the possible similarity candidates for each query object, after accessing only a few of their non-zero values. The pruning process results in unpredictable memory access pat- terns that can reduce search efficiency. In this context, we introduce pL2AP, which efficiently solves the AllPairs cosine similarity search problem in a multi-core environment. Our method uses a number of cache-tiling optimizations, combined with fine-grained dynamically balanced parallel tasks, to solve the problem 1.5x– 238x faster than existing parallel baselines on datasets with hundreds of millions of non-zeros.
Research topics: Data mining | Parallel processing