Part of the Santh security research ecosystem.

dedup

High-performance dataset deduplication for ML training data using MinHash + LSH.

Features

MinHash + LSH: Industry-standard near-duplicate detection with configurable similarity thresholds
Fast Hashing: Efficient hash computation for high throughput
Streaming: Process billions of documents without loading all into memory
tenshift Integration: Plugs into data pipelines as a Transform
Configurable: Tune signature size, band count, and thresholds for your data
Robust: Fuzz-quality input handling, zero unwrap in production code

Quick Start

use dedup::{Config, DedupTransformer};
use dedup::tenshift::Sample;
use tenshift_core::sample::Tensor;

let config = Config::default()
    .with_similarity_threshold(0.9);

let mut dedup = DedupTransformer::new(config)?;

// Add documents
dedup.push(Sample::new().with("text", Tensor::bytes(b"the quick brown fox".to_vec())));
dedup.push(Sample::new().with("text", Tensor::bytes(b"the quick brown fox".to_vec())));

// Get deduplicated results: the exact duplicate collapses to one entry.
let unique = dedup.finish_batch();
assert_eq!(unique.len(), 1);
# Ok::<(), dedup::Error>(())

How It Works

┌─────────────┐     ┌──────────────┐     ┌─────────────┐     ┌─────────────┐
│   Shingle   │────▶│   MinHash    │────▶│  LSH Bands  │────▶│   Cluster   │
│  (k-grams)  │     │  (fast hash) │     │  (buckets)  │     │    Output   │
└─────────────┘     └──────────────┘     └─────────────┘     └─────────────┘

Shingling: Convert documents to sets of k-grams (overlapping subsequences)
MinHash: Compress documents to small signatures preserving Jaccard similarity
LSH: Band signatures such that similar documents collide in buckets
Clustering: Group colliding documents and output unique representatives

Configuration

let config = dedup::Config::new(
    128,    // signature size (hash functions)
    16,     // LSH bands
    5,      // shingle size
    0.9,    // similarity threshold
)?;
# Ok::<(), dedup::Error>(())

Parameter Guide

Parameter	Default	Description
`signature_size`	128	Number of hash functions. Higher = more accurate but slower
`num_bands`	16	LSH bands. Higher = more sensitive but more false positives
`shingle_size`	5	k-gram length. 4-7 works well for text
`threshold`	0.9	Similarity threshold. 0.85-0.95 recommended

tenshift Integration

use dedup::{Config, StatefulDedupTransform};
use dedup::tenshift::Sample;
use tenshift_core::sample::Tensor;
use tenshift_core::transform::StatefulTransform;

let config = Config::default();
let mut dedup = StatefulDedupTransform::new(config)?;

// In your pipeline
let samples = vec![
    Sample::new().with("text", Tensor::bytes(b"hello world".to_vec())),
    Sample::new().with("text", Tensor::bytes(b"hello world".to_vec())),
];
for sample in samples {
    let output = dedup.push(sample);
    // output is empty until finish() is called
    assert!(output.is_empty());
}

let unique = dedup.finish();
assert_eq!(unique.len(), 1);
# Ok::<(), dedup::Error>(())

Performance

Benchmarked on AMD Ryzen 9 5950X:

Operation	Throughput
MinHash (128 sig)	~50,000 docs/sec
MinHash (256 sig)	~25,000 docs/sec
LSH Insert	~100,000 ops/sec
Batch (1000 docs)	~30ms

Architecture

MinHash Theory

MinHash estimates Jaccard similarity between sets:

J(A,B) = |A ∩ B| / |A ∪ B|
MinHash approximates this by comparing hash signatures
Expected error: √(s(1-s)/k) where s is similarity, k is signature size

LSH Theory

LSH reduces O(n²) comparisons to O(n):

Signature split into b bands of r rows each
Probability of collision for similarity s: 1 - (1 - s^r)^b
Threshold (S-curve inflection): t ≈ (1/b)^(1/r)

Testing

cargo test
cargo test --release  # For benchmarks
cargo clippy -- -D warnings

License

MIT License - See LICENSE file for details.

Authors

Santh 64453045+santhreal@users.noreply.github.com

santh-dedup 0.1.4