MinHash, SimHash, and Bloom Filters

6.1 MinHash

python
Run Inline
import numpy as np
def minhash_signature(set_of_ints, num_hashes=100):
    max_int = 2**32 - 1
    seeds = np.random.randint(0, max_int, num_hashes)
    sig = np.full(num_hashes, np.inf)
    for val in set_of_ints:
        for i, seed in enumerate(seeds):
            h = (seed * val + seed) % max_int
            sig[i] = min(sig[i], h)
    return sig

6.2 Bloom Filter

• No false negatives (if "no", definitely not in set)
• False positives possible (if "yes", might not be in set) Operations: add(x), query(x) — both $O(k)$ where $k$ is number of hash functions. False positive rate: $(1 - e^{-kn/m})^k$ where $m$ is bits and $n$ is elements. Join Discord PreviousLocality-Sensitive HashingNextRandomized Regression