datasketch

Use datasketch.MinHashLSHEnsemble to find sets in a collection that have a high degree of containment relative to a query set. Unlike Jaccard similarity, which can be biased by large set sizes, containment measures the fraction of the query set $Q$ contained in a set $X$ ($Containment = \frac{|Q \cap X|}{|Q|}$).

To use the ensemble:

1. Create MinHash objects for your sets.
2. Initialize MinHashLSHEnsemble with a threshold, num_perm, and num_part.
3. Index your data using an iterable of (key, minhash, size) tuples.
4. Query the index using a MinHash object and the size of the query set.

from datasketch import MinHashLSHEnsemble, MinHash

set1 = set(["cat", "dog", "fish", "cow"])
set2 = set(["cat", "dog", "fish", "cow", "pig", "elephant", "lion", "tiger",
             "wolf", "bird", "human"])
set3 = set(["cat", "dog", "car", "van", "train", "plane", "ship", "submarine",
             "rocket", "bike", "scooter", "motorcyle", "SUV", "jet", "horse"])

# Create MinHash objects
m1 = MinHash(num_perm=128)
m2 = MinHash(num_perm=128)
m3 = MinHash(num_perm=128)
for d in set1:
    m1.update(d.encode('utf8'))
for d in set2:
    m2.update(d.encode('utf8'))
for d in set3:
    m3.update(d.encode('utf8'))

# Create an LSH Ensemble index with threshold and number of partition settings.
lshensemble = MinHashLSHEnsemble(threshold=0.8, num_perm=128, 
    num_part=32)

# Index takes an iterable of (key, minhash, size)
lshensemble.index([("m2", m2, len(set2)), ("m3", m3, len(set3))])

# Check for membership using the key
print("m2" in lshensemble)
print("m3" in lshensemble)

# Using m1 as the query, get an result iterator 
print("Sets with containment > 0.8:")
for key in lshensemble.query(m1, len(set1)):
    print(key)

LSHBloom is a space-efficient alternative to MinHashLSH. While MinHashLSH returns candidate duplicates, MinHashLSHBloom returns a binary signal (0 or 1) indicating whether a query set has a Jaccard similarity $\ge T$ with any other set in the collection.

To use it, you must provide an estimate of the dataset size (n) and the acceptable false positive overhead per Bloom filter (fp) during initialization.

from datasketch import MinHash, MinHashLSHBloom

set1 = set(['minhash', 'is', 'a', 'probabilistic', 'data', 'structure', 'for',
            'estimating', 'the', 'similarity', 'between', 'datasets'])
set2 = set(['minhash', 'is', 'a', 'probability', 'data', 'structure', 'for',
            'estimating', 'the', 'similarity', 'between', 'documents'])
set3 = set(['minhash', 'is', 'probability', 'data', 'structure', 'for',
            'estimating', 'the', 'similarity', 'between', 'documents'])

m1 = MinHash(num_perm=128)
m2 = MinHash(num_perm=128)
m3 = MinHash(num_perm=128)
for d in set1:
    m1.update(d.encode('utf8'))
for d in set2:
    m2.update(d.encode('utf8'))
for d in set3:
    m3.update(d.encode('utf8'))

# Create LSHBloom index
# threshold: Jaccard similarity threshold
# num_perm: number of permutations
# n: estimated number of sets in the dataset
# fp: allowable false positive rate per Bloom filter
lsh = MinHashLSHBloom(threshold=0.5, num_perm=128, n=100, fp=0.001)
lsh.insert("m2", m2)
lsh.insert("m3", m3)

is_duplicate = lsh.query(m1)
print("Is Duplicate: ", is_duplicate)

You can optionally run part of MinHash.update_batch on a CUDA GPU using CuPy. Note that hashing and permutation generation still occur on the CPU; only permutation application and min-reduction are offloaded to the GPU.

Configuration: Use the gpu_mode argument in the MinHash constructor:

• 'disable' (default): Always use CPU.
• 'detect': Use GPU if available, otherwise fallback to CPU.
• 'always': Require GPU; raises RuntimeError if no CUDA device is available.

Installation: CuPy is an optional dependency. Install the version matching your CUDA version (e.g., pip install cupy-cuda12x).

Tip: If you are in a cloud environment with an NVIDIA driver but no local CUDA Toolkit, install with the CTK extra to avoid RuntimeError: Failed to find CUDA headers: pip install "cupy-cuda12x[ctk]".

# Force CPU only
m = MinHash(num_perm=256, gpu_mode="disable")
m.update_batch(data)

# Require GPU (raises RuntimeError if no CUDA device)
m = MinHash(num_perm=256, gpu_mode="always")
m.update_batch(data)