Skip to content

MinHash Fingerprinting

MinHash is a locality-sensitive hashing algorithm that estimates Jaccard similarity between document shingle sets. PrimeStamp uses MinHash to enable fast approximate similarity search across large document corpora, making it possible to detect near-duplicate documents without pairwise comparison.

How It Works

  1. The document is split into overlapping shingles (n-grams of words or characters).
  2. A family of hash functions maps each shingle to integer values.
  3. For each hash function, only the minimum hash value is kept, producing a compact signature.
  4. The fraction of matching signature positions between two documents approximates their Jaccard similarity.

Quick Start

from primestamp.fingerprint.minhash import MinHashGenerator, ShingleMode

# Create a generator with 128 hash functions and 3-word shingles
gen = MinHashGenerator(num_hashes=128, shingle_size=3)

# Generate signatures
sig1 = gen.generate(b"The quick brown fox jumps over the lazy dog")
sig2 = gen.generate(b"The quick brown fox leaps over the lazy dog")

# Compare
similarity = sig1.jaccard_similarity(sig2)
print(f"Jaccard similarity: {similarity:.4f}")

For large collections, use the LSH (Locality-Sensitive Hashing) index to avoid brute-force pairwise comparison.

gen = MinHashGenerator(num_hashes=128, shingle_size=3)
index = gen.create_lsh_index(num_bands=16)

# Index documents
for doc_id, content in documents.items():
    sig = gen.generate(content)
    index.insert(doc_id, sig)

# Query for similar documents
query_sig = gen.generate(b"New document to search for...")
results = index.find_similar(query_sig, threshold=0.5)
for doc_id, score in results:
    print(f"{doc_id}: {score:.4f}")

Configuration

Parameter Type Default Description
num_hashes int 128 Number of hash functions (signature size). Higher = more accurate but larger.
shingle_size int 3 N-gram length for shingling.
shingle_mode ShingleMode WORD WORD for word-level shingles, CHARACTER for character-level.
seed int 42 Random seed for reproducible hash functions.
normalize bool True Lowercase and collapse whitespace before shingling.

Shingle Modes

# Word-level shingles (default) - better for natural language
gen_word = MinHashGenerator(shingle_mode=ShingleMode.WORD, shingle_size=3)

# Character-level shingles - better for short texts or code
gen_char = MinHashGenerator(shingle_mode=ShingleMode.CHARACTER, shingle_size=5)

Choosing Parameters

  • num_hashes=128 gives roughly 8% standard error on similarity estimates.
  • num_hashes=256 reduces error to about 6% at the cost of double the storage.
  • For LSH, the number of bands controls the recall/precision trade-off. More bands increases recall but may return more false positives.

Serialization

Signatures can be serialized for storage and later comparison.

# Serialize
data = sig1.to_dict()

# Deserialize
from primestamp.fingerprint.minhash import MinHashSignature
sig_restored = MinHashSignature.from_dict(data)

Factory Function

Use create_minhash_generator for quick setup.

from primestamp.fingerprint.minhash import create_minhash_generator

gen = create_minhash_generator(num_hashes=256, shingle_size=4, mode="character")

When to Use MinHash

MinHash is ideal for set similarity (Jaccard index). If you need weighted token frequency similarity (cosine distance), see SimHash instead.