PL2AP: Fast Parallel Cosine Similarity Search
| David C. Anastasiu and George Karypis |
| 5th Workshop on Irregular applications: Architectures and Algorithms, Supercomputing, 2015 |
Download Paper  |
| Abstract 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 |