PaperlayerView exact revision on arXiv

Source-linked AI summary

b-Bit Minwise Hashing

Ping Li, Arnd Christian Konig

arXiv:0910.3349v1cs.DScs.DBcs.IR

TL;DR

Minwise hashing estimates set similarity but traditionally stores 64 or 40 bits per hashed value, creating storage and computational costs. The paper develops a theoretical framework for storing only the lowest b bits and derives an unbiased resemblance estimator. For resemblance above 0.5, b = 1 can reduce storage by at least 21.3-fold versus 64 bits or 10.7-fold versus 32 bits in the least favorable scenario.

  • Problem

    Minwise hashing is widely used for set-similarity estimation, but storing each hashed value with many bits limits storage and computational efficiency.

  • Method

    The paper analyzes b-bit minwise hashing, stores the lowest b bits of each hashed value, proves its theoretical properties, and derives an unbiased estimator for resemblance.

  • Results

    For resemblance ≥0.5, b = 1 yields at least 10.7–16-fold space improvement over 32-bit storage and at least 21.3–32-fold improvement over 64-bit storage, even in the worst case.

  • Takeaways & Limitations

    Low-bit minwise hashing can substantially reduce storage and improve computational efficiency with minimal modification to the original algorithm.

  • Takeaways & Limitations

    Combining two bits from different hashed values is mostly useful when applications care about pairs with very high similarities.

Abstract

from arXiv · show

This paper establishes the theoretical framework of b-bit minwise hashing. The original minwise hashing method has become a standard technique for estimating set similarity (e.g., resemblance) with applications in information retrieval, data management, social networks and computational advertising. By only storing the lowest $b$ bits of each (minwise) hashed value (e.g., b=1 or 2), one can gain substantial advantages in terms of computational efficiency and storage space. We prove the basic theoretical results and provide an unbiased estimator of the resemblance for any b. We demonstrate that, even in the least favorable scenario, using b=1 may reduce the storage space at least by a factor of 21.3 (or 10.7) compared to using b=64 (or b=32), if one is interested in resemblance > 0.5.

1. INTRODUCTION

The paper motivates reducing the storage and computational costs of minwise hashing for set-similarity estimation, especially in massive datasets. It introduces b-bit minwise hashing, whose theory supports using as few as 1 or 2 bits while preserving accuracy when resemblance is reasonably high.

  • Motivation: Set-intersection size measures un-normalized similarity and underlies tasks in information retrieval, databases, and machine learning.Resemblance provides a normalized similarity measure, and resemblance distance is a metric.
  • Motivation: Large-scale intersection computation is challenging, including duplicate detection for web documents represented as bags of contiguous-word shingles.The number of possible 5-shingles is enormous, motivating compact similarity representations.
  • Minwise Hashing: Minwise hashing estimates set similarity through hashed samples and has been applied to duplicate removal, advertising, social networks, graphs, and web-content analysis.The paper situates its method within substantial prior theoretical, methodological, and application-oriented work.
  • Minwise Hashing: 64-bit samples require storage proportional to the bit width, so reducing bits per hashed value can save storage and improve computational efficiency.A sample is a minimum hashed value, and total storage per set is bk bits for sample size k.
  • b-Bit Minwise Hashing: The proposed framework stores only the lowest b bits of each hashed value, with b = 1 or b = 2 suggested as compact alternatives to 64- or 40-bit storage.Using fewer bits increases variance at fixed sample size, but the theory predicts little extra sampling is needed when R ≥0.5.
  • b-Bit Minwise Hashing: 21.3-fold space improvement is possible with b = 1 versus 64-bit storage when R = 0.5, even after tripling the sample size to offset the variance increase.At b = 1 and R = 0.5, the estimation variance increases at most by a factor of 3.

2. THE FUNDAMENTAL RESULTS

The fundamental results characterize the probability and variance of b-bit minwise hashing in terms of resemblance, set-size ratios, and bit width. They yield an unbiased resemblance estimator and quantify the variance–space trade-off, showing when smaller b is preferable.

  • 2. THE FUNDAMENTAL RESULTS: The analysis applies a random permutation to two sets and records the lowest b bits of their minimum hashed values.The sets lie in a universe Ω of size D, with set sizes f1 and f2 and intersection size a.
  • 2. THE FUNDAMENTAL RESULTS: For fixed set-size ratios, Aj,b decreases monotonically as b increases; for fixed b, it decreases monotonically as rj increases.The theorem assumes D is large and bounds Aj,b by 1.
  • 2. THE FUNDAMENTAL RESULTS: Theorem 1 determines the relevant matching probability from resemblance R and the set-size ratios r1 and r2.This relationship provides the basis for estimating resemblance from low-bit samples.
  • 2. THE FUNDAMENTAL RESULTS: The paper derives an unbiased estimator R̂b from the lowest bits observed across k minwise-independent permutations.The bit observations are indexed by permutation and bit position, and their binomial structure supports the estimator.
  • 2. THE FUNDAMENTAL RESULTS: As b decreases, storage per sample falls but estimation variance at the same sample size k increases; for large b, the variance approaches that of original minwise hashing.The auxiliary variance terms become negligible as b grows, and b ≥32 can essentially be treated as having them equal to zero.
  • 2.2 The Variance-Space Trade-off: The storage factor B(b; R, r1, r2) quantifies the variance–space trade-off, with lower values preferred and ratios comparing compact b-bit storage against larger baselines.The ratio directly measures improvement from using b2 bits instead of b1 bits.
  • 2.2 The Variance-Space Trade-off: When r1 and r2 are near 1, b = 1 is desirable across nearly all R; when both are near 0, b = 1 is advantageous mainly for R ≥0.4.For small R and small set-size ratios, larger values such as b ≥2 may be preferable.
  • 2.2 The Variance-Space Trade-off: The relative improvement of using b = 1 increases with resemblance R under the stated equal-ratio and large-b assumptions.The analysis treats A1,b as zero for b1 ≥32 when r1 = r2.

3. EXPERIMENTS

The experiments validate the unbiased b-bit resemblance estimator and its theoretical variance, then assess retrieval accuracy and storage savings on word pairs and news documents. Across these evaluations, smaller signatures generally preserve retrieval behavior while substantially reducing storage, especially for resemblance thresholds at least 0.5.

  • Experimental design: Three experiments used 2633-word data for theory checks and 10000 crawled news articles for duplicate detection.The news experiment evaluated 49995000 document pairs.
  • 3.1 Experiment 1: The estimator was empirically unbiased, with very small biases and no systematic bias across the tested word pairs.Figure 3 used 25000 simulations at each sample size k.
  • 3.1 Experiment 1: The theoretical variance formula accurately matched empirical MSEs, whose theoretical and empirical curves overlapped.Because MSE equals variance when the estimator is unbiased, the overlap supports the variance prediction.
  • 3.2 Experiment 2: At equal sample size, precision was lower for b = 1 than original minwise hashing at small thresholds, while b ≥3 performed similarly.Recall generally did not distinguish estimators unless b = 1.
  • 3.2–3.3 Experiments: 10–18-fold space improvements were observed for b = 1 at thresholds R0 ≥0.5, relative to 32-bit original minwise hashing.In the news experiment, b = 4 had nearly indistinguishable precision from the 32-bit baseline, suggesting an 8-fold space improvement; b = 1 or 2 typically achieved 10-fold to 15-fold savings at high precision.

4. DISCUSSION: COMBINING BITS FOR ENHANCING PERFORMANCE

Combining two bits from separate permutations can improve estimation for highly similar pairs, but requires twice as many permutations and remains unsuitable when resemblance is not high.

  • For resemblance about R ≥ 0.4, b = 1 outperforms b > 1 even in the least favorable situation, motivating exploration of b < 1.
  • The b = 1/2 estimator combines two bits from two permutations, so generating k samples requires 2× k permutations while storing each sample in 1 bit.
  • As R →1, ˆR1/2 does twice as well as ˆR1.
  • Empirically, ˆR1/2 performs superbly for KONG-HONG and considerably better for OF-AND, but similarly to ˆR1 for UNITED-STATES with R = 0.591.
  • For LOW-PAY with R = 0.112, ˆR1/2 has very large theoretical variance but not-too-bad empirical performance because of the variance-bias trade-off.
  • The combined-bits idea is mostly useful for applications concerned with pairs of very high similarities.

5. CONCLUSION

The paper develops b-bit minwise hashing by storing only the lowest b bits of each hashed value, requiring minimal changes to minwise hashing. For resemblance at least 0.5, b=1 can substantially reduce storage, with further enhancement possible by combining bits when similarity is very high.

  • Minwise hashing is a standard approach for efficiently computing set similarity in massive datasets, including duplicate detection.Prior studies commonly stored each hashed value using 64 or 40 bits.
  • Storing only the lowest b bits establishes the paper’s theoretical framework for b-bit minwise hashing.The method requires only minimal modification to the original minwise hashing algorithm.
  • 10.7–16-fold space improvement is possible with b=1 versus 32-bit hashed values when resemblance is at least 0.5.The bound applies even in the worst case.
  • At least 21.3–32-fold space improvement is possible with b=1 versus 64-bit hashed values.This improvement is larger because the original hashed values use twice as many bits as the 32-bit baseline.
  • Combining 2 bits from different hashed values can further enhance the improvement when the target similarity is very high.

A. PROOF OF THEOREM 1

The proof models two sets under a random permutation, derives the joint minimum-value probabilities, and extends the b=1 result to general b. It then establishes monotonicity properties of the resulting expression under the large-universe approximation.

  • Set and permutation setup: The proof represents two sets as subsets of a universe and records their sizes and intersection size.The notation uses S1, S2, universe size D, set sizes f1 and f2, and intersection size a.
  • Set and permutation setup: A random permutation defines minimum values z1 and z2, whose lowest bits e1,i and e2,i are used in the b-bit analysis.
  • Probability derivation: The joint probability Pr(z1=i, z2=j, i<j) is decomposed into P1+P2 after introducing a basic probability formula.
  • Probability derivation: The probability terms are interpreted by randomly assigning f1+f2−a balls to D locations across three disjoint set regions.The unrestricted assignment count is P3, and separate cases are considered to understand P1 and P3.
  • Theorem completion: A1,b decreases monotonically with b, and A1,b also decreases monotonically with r1, completing the proof.
Loading 0910.3349v1…