sketchir

Sketching primitives for retrieval.

MinHash, SimHash, and LSH indexes for near-duplicate detection and approximate similarity search.

[dependencies]
sketchir = "0.6"

Best starting points

• Near-duplicate detection: MinHashTextLSH + BlockingConfig
• SimHash fingerprints: SimHashFingerprint / SimHashLSH
• Dense-vector LSH (batch): LSHIndex -- multi-table random projection, add/build/search lifecycle
• Dense-vector LSH (incremental): DenseSimHashLSH -- SimHash + Hamming-1 probing, no build step

Tuning knobs (BlockingConfig)

Example (MinHash blocking)

use sketchir::{BlockingConfig, MinHashTextLSH};

let cfg = BlockingConfig::default();
let mut index = MinHashTextLSH::new(cfg).unwrap();
index.insert_text("a", "hello world");
index.insert_text("b", "hello  world!");

let pairs = index.candidate_pairs();
assert!(!pairs.is_empty());

Examples

Runnable examples live in examples/:

• dedup_documents indexes a document set and returns candidate near-duplicate pairs via MinHash LSH blocking.
• minhash_jaccard_validation checks the MinHash Jaccard estimate against the exact Jaccard index, confirming the sketch is accurate before trusting it at scale.
• updatable_store exercises the optional durable store: add documents, checkpoint, delete one, reopen, and query ranked near-duplicates. Run with --features store.

Updatable index (store feature)

store::UpdatableIndex wraps the MinHash near-duplicate index in a durable, segmented store (segstore): incremental add/delete, a write-ahead log, checkpoint, compaction, and crash recovery. The per-segment LSH blocks are cached and persisted as sidecars, so restart loads unchanged MinHash blocks instead of rebuilding them. near_duplicates_with_similarity ranks durable candidates by estimated Jaccard similarity while reusing one query signature across all segments. near_duplicates_min_shared_bands requires repeated band collisions when you want fewer, higher-precision candidates. store::SnapshotIndex opens the last checkpoint manifest and queries sidecars first, so source text batches are read only when a sidecar is missing or unusable. Opt-in; the default build does not depend on segstore.

For measurement, cargo run --release --features store --example store_reopen_diagnostics prints the first snapshot-query cost with persisted MinHash sidecars present versus after deleting those sidecars and forcing source-segment rebuilds.

documents: 1000, flush threshold: 200
sidecars loaded path: 5
sidecars rebuild path before/after delete: 5/0
first snapshot query with sidecars: 2369 us
first snapshot query after deleting sidecars: 37418 us
matching candidates: 1
query doc present: true

License

MIT OR Apache-2.0