BagMinHash - Minwise Hashing Algorithm for Weighted Sets

Abstract

Minwise hashing has become a standard tool to calculate signatures which allow direct estimation of Jaccard similarities. While very efficient algorithms already exist for the unweighted case, the calculation of signatures for weighted sets is still a time consuming task. BagMinHash is a new algorithm that can be orders of magnitude faster than current state of the art without any particular restrictions or assumptions on weights or data dimensionality. Applied to the special case of unweighted sets, it represents the first efficient algorithm producing independent signature components. A series of tests finally verifies the new algorithm and also reveals limitations of other approaches published in the recent past.

arXiv comment10 pages, KDD 2018

References in corpus (6)

• Consistent Weighted Sampling Made Fast, Small, and Easy
• Optimal Densification for Fast and Accurate Minwise Hashing
• Optimal Discrete Uniform Generation from Coin Flips, and Applications
• SuperMinHash - A New Minwise Hashing Algorithm for Jaccard Similarity Estimation
• Topic modeling of public repositories at scale using names in source code
• Improved Consistent Weighted Sampling Revisited

Cited by in corpus (7)

• A Memory-Efficient Sketch Method for Estimating High Similarities in Streaming Sets
• ProbMinHash -- A Class of Locality-Sensitive Hash Algorithms for the (Probability) Jaccard Similarity
• SetSketch: Filling the Gap between MinHash and HyperLogLog
• DotHash: Estimating Set Similarity Metrics for Link Prediction and Document Deduplication
• DartMinHash: Fast Sketching for Weighted Sets
• Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon
• Fast Generating A Large Number of Gumbel-Max Variables