Crate dedup 

dedup - High-performance dataset deduplication for ML training data

A MinHash + LSH implementation for finding near-duplicate documents in massive datasets. Designed for streaming operation to handle billions of documents without loading all into memory.

Quick Start

use dedup::{Config, DedupTransformer};

let config = Config::default()
    .with_similarity_threshold(0.85)
    .with_num_bands(16);

let dedup = DedupTransformer::new(config).unwrap();

Architecture

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

MinHash + LSH Theory

• Shingling: Convert documents to sets of k-grams (overlapping subsequences)
• MinHash: Compress document to a small signature while preserving Jaccard similarity
• LSH: Band signatures such that similar documents collide in at least one bucket
• Threshold: Documents with estimated Jaccard ≥ threshold are considered duplicates

Re-exports

pub use shingle::ShingleIterator;

Modules

shingle

Shingling (k-gram generation) for text documents.

tenshift

Re-export tenshift types for convenience.

Structs

Config

DedupTransformer

A transform that deduplicates samples using MinHash + LSH.

DuplicateCluster

A cluster of duplicate documents.

FastHasher

A fast hasher for computing multiple hash values efficiently.

LshIndex

LSH index for finding candidate similar document pairs.

MinHashSignature

A MinHash signature for a document.

MinHasher

MinHasher computes MinHash signatures from documents.

StatefulDedupTransform

A stateful deduplication transform that buffers samples.

Enums

Error

All errors that can occur during deduplication.

Constants

DEFAULT_NUM_BANDS

Default number of LSH bands.

DEFAULT_SHINGLE_SIZE

Default shingle size in bytes/characters.

DEFAULT_SIGNATURE_SIZE

Default number of hash functions (signature size).

DEFAULT_SIMILARITY_THRESHOLD

Default similarity threshold for considering documents as duplicates.

Functions

candidate_probability

Estimate the false positive rate given LSH parameters.

compute_rows_per_band

Compute the number of rows per band given signature size and num bands.

hash_bytes

Compute a fast, non-cryptographic hash of a byte slice.

optimize_lsh_params

Find the optimal LSH parameters for a given similarity threshold.

Type Aliases

Result

Convenience result type.