  The Exact Set Similarity Join problem aims to find all similar sets between
two collections of sets, with respect to a threshold and a similarity function
such as overlap, Jaccard, dice or cosine. The naive approach verifies all pairs
of sets and it is often considered impractical due the high number of
combinations. So, Exact Set Similarity Join algorithms are usually based on the
Filter-Verification Framework, that applies a series of filters to reduce the
number of verified pairs. This paper presents a new filtering technique called
Bitmap Filter, which is able to accelerate state-of-the-art algorithms for the
exact Set Similarity Join problem. The Bitmap Filter uses hash functions to
create bitmaps of fixed b bits, representing characteristics of the sets. Then,
it applies bitwise operations (such as xor and population count) on the bitmaps
in order to infer a similarity upper bound for each pair of sets. If the upper
bound is below a given similarity threshold, the pair of sets is pruned. The
Bitmap Filter benefits from the fact that bitwise operations are efficiently
implemented by many modern general-purpose processors and it was easily applied
to four state-of-the-art algorithms implemented in CPU: AllPairs, PPJoin,
AdaptJoin and GroupJoin. Furthermore, we propose a Graphic Processor Unit (GPU)
algorithm based on the naive approach but using the Bitmap Filter to speedup
the computation. The experiments considered 9 collections containing from 100
thousands up to 10 million sets and the joins were made using Jaccard
thresholds from 0.50 to 0.95. The Bitmap Filter was able to improve 90% of the
experiments in CPU, with speedups of up to 4.50x and 1.43x on average. Using
the GPU algorithm, the experiments were able to speedup the original CPU
algorithms by up to 577x using an Nvidia Geforce GTX 980 Ti.
