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 patterns 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--232x faster than existing parallel baselines on datasets
with hundreds of millions of non-zeros.