Bitmap Filter: Speeding Up Exact Set Similarity Joins With Bitwise Operations

Abstract

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

Stats

• citations2
• S2 citations—
• github stars0
• HF likes0
• heat score3.58
• arxiv keysandes2017bitmap

Related papers

• Efficient Bitmap-based Indexing And Retrieval Of Similarity Search Image Queries (2019)0.00
• Subsets And Supermajorities: Optimal Hashing-based Set Similarity Search (2019)5.84
• Xling: A Learned Filter Framework For Accelerating High-dimensional Approximate Similarity Join (2024)0.00
• Efficient Similarity Search In Dynamic Data Streams (2016)0.00
• Billion-scale Similarity Search Using A Hybrid Indexing Approach With Advanced Filtering (2025)4.52
• Lsf-join: Locality Sensitive Filtering For Distributed All-pairs Set Similarity Under Skew (2020)6.34
• Set Similarity Search Beyond Minhash (2016)10.74
• Interleaved Composite Quantization For High-dimensional Similarity Search (2019)0.00