# dedup - Specification
## Overview
`dedup` is a Rust crate for near-duplicate detection in ML training datasets using MinHash + Locality Sensitive Hashing (LSH). It converts documents into fixed-size signatures via k-gram shingling and permutation hashing, then bands those signatures so that similar documents collide in shared LSH buckets. Candidate pairs are verified against a configurable Jaccard-similarity threshold, and duplicates are grouped into clusters. The crate integrates with the `tenshift` pipeline framework and supports both streaming and batch operation.
## Architecture
The crate is organized as a pipeline of five stages:
1. **Shingling (`shingle`)** - `ShingleIterator` and `HashedShingleIterator` produce overlapping byte-level k-grams from raw documents. A `WordShingleIterator` is also provided for word-level n-grams.
2. **Fast hashing (`fast_hash`)** - Shingles are hashed with a MurmurHash3-inspired 64-bit function. MinHash uses a family of linear permutation hashes `(a·x + b) mod (2^61 − 1)` generated by SplitMix64.
3. **MinHash (`minhash`)** - `MinHasher` computes a signature (vector of `u32`) by taking the minimum hash value per permutation across all shingles. `MinHashSignature` supports similarity estimation and band extraction.
4. **LSH indexing (`lsh`)** - `LshIndex` splits each signature into `num_bands` of `rows_per_band` values. Each band is hashed into a bucket (`band_idx → bucket_hash → doc_ids`). Documents sharing any bucket are candidate duplicates.
5. **Clustering & transform (`cluster`, `transform`)** - Candidate pairs are verified with exact signature similarity. Connected components of verified pairs form `DuplicateCluster`s. `DedupTransformer` and `StatefulDedupTransform` wrap the engine as a `tenshift` pipeline stage.
Data flows: `Document → shingles → hashed shingles → MinHash signature → LSH bands → candidate pairs → verified duplicates → clusters`.
## Guarantees
- **Determinism**: Given the same `seed`, shingle hashes, MinHash signatures, and LSH band hashes are deterministic.
- **Threshold enforcement**: Any document returned as a duplicate has estimated Jaccard similarity ≥ `similarity_threshold` with at least one other document in its cluster.
- **Cluster transitivity**: Duplicate clusters are connected components; if A~B and B~C, they are placed in the same cluster even if A and C are below threshold.
- **Config validation**: `Config::new` rejects invalid states (e.g., `signature_size` not divisible by `num_bands`, threshold outside `(0.0, 1.0]`, zero shingle size).
- **Bounded bucket growth**: Individual LSH buckets are capped at 10,000 entries to limit memory consumption from collisions.
## Public API
**Key types**
- `Config` - Builder for signature size, number of LSH bands, shingle size, similarity threshold, memory limit, and seed.
- `MinHasher` - Computes `MinHashSignature` from bytes, strings, or pre-hashed shingles.
- `MinHashSignature` - Holds the signature vector and `doc_id`; provides `similarity()`, `band()`, and `band_hash()`.
- `LshIndex` - Insert signatures, query candidates, verify similarity, and extract clusters.
- `DedupTransformer` / `StatefulDedupTransform` - `tenshift` pipeline transforms that buffer samples, run deduplication, and output unique items.
- `DuplicateCluster` - Result type containing `id`, `representative` (lowest doc index), and `indices`.
- `LshStats` - Runtime statistics including bucket counts and estimated recall / false-positive rate.
- `ShingleIterator` / `HashedShingleIterator` - Lazy k-gram iterators.
**Key functions**
- `Config::new(signature_size, num_bands, shingle_size, threshold) -> Result<Config>`
- `MinHasher::new(&Config) -> Result<MinHasher>`
- `MinHasher::compute(&self, data: &[u8], doc_id: usize) -> Result<MinHashSignature>`
- `LshIndex::insert(&mut self, signature) -> Result<Vec<usize>>` - returns candidate doc IDs.
- `LshIndex::find_clusters(&mut self) -> &[DuplicateCluster]`
- `LshIndex::get_unique_indices(&self) -> Vec<usize>`
- `compute_rows_per_band`, `candidate_probability`, `optimize_lsh_params` - LSH parameter utilities.
## Error handling
All fallible operations return `Result<T>` alias to `std::result::Result<T, Error>`:
- `Error::InvalidConfig { reason, fix }` - Bad parameters (e.g., `signature_size % num_bands != 0`), missing text field, non-UTF-8 text, or `doc_id` exceeding the 100M hard limit.
- `Error::DocumentTooLarge { size, max }` - Document exceeds `max_document_size` (default 10 MiB).
- `Error::EmptyDocument { index }` - Document is empty or shorter than the shingle size.
- `Error::HashingFailed { reason }` - Internal hash computation failure (e.g., overflow).
- `Error::MemoryLimitExceeded { usage_bytes }` - Estimated in-memory state exceeds the configured limit.
- `Error::Io(std::io::Error)` - IO failures during processing.
## Performance characteristics
- **Shingling**: O(L) time per document, O(1) extra memory (streaming iterator).
- **MinHash computation**: O(L · k) time where `k = signature_size`; O(k) memory per signature.
- **LSH insert/query**: O(k) time per document (band hashing and bucket lookup).
- **Candidate verification**: Avoids O(n²) pairwise comparisons; only candidates sharing an LSH bucket are checked.
- **Clustering**: O(d · c) where `d` is number of documents and `c` is average candidates per document; BFS over connected components.
- **Memory**: Holds all signatures (`doc_count × signature_size × 4` bytes) plus LSH bucket vectors and a `BTreeMap` of signatures. Default 4 GiB memory limit; `Config` provides `estimated_memory_per_document()` and `max_documents_in_memory()`.
- **Accuracy trade-off**: MinHash similarity variance is ≈ `s(1−s)/k`. Default `k = 128` gives standard deviation ≈ 0.044 at `s = 0.5`.
## Limitations
- **Approximate**: MinHash + LSH is a probabilistic filter. False negatives (missing true duplicates) and false positives (spurious candidates) are possible.
- **Text-oriented**: The pipeline transform extracts a configurable text field and expects UTF-8. Binary deduplication requires using `MinHasher`/`LshIndex` directly on raw bytes.
- **Memory-bound**: The entire LSH index and all signatures reside in RAM. There is no out-of-core or distributed mode.
- **Single-index scope**: Deduplication does not span separate `LshIndex` instances.
- **Bucket cap**: Buckets clamp at 10,000 entries; extreme collision attacks or very high similarity universal documents can cause missed duplicates.
- **Doc ID limit**: `doc_id` is capped at 100,000,000 to prevent adversarial unbounded allocation.
- **No semantic understanding**: Character- or word-level overlap does not capture paraphrase or semantic equivalence.