gaoya

Gaoya is a Rust library that implements Locality Sensitive Hashing (LSH) algorithms — MinHash (in 8, 16, 32, and 64-bit signature widths) and SimHash (64 and 128-bit) — for indexing and querying large collections of text documents. It’s built for two core use cases: deduplication, finding exact and near-duplicate documents in a corpus, and clustering, grouping similar documents together without comparing every pair.

The library is multi-threaded via rayon, exposes a banded LSH index that trades a small amount of recall for large gains in query speed, and ships with a parallel, lock-free clustering algorithm built on atomic pointer swaps. A PyO3-based Python package (pip install gaoya) wraps the same Rust core, so the same signatures and indexes are usable from Python pipelines as well as native Rust code.

What You Get

• MinHash signatures in 8, 16, 32, and 64-bit widths for Jaccard-similarity estimation
• SimHash signatures (64-bit and 128-bit) for Hamming-distance style near-duplicate detection
• A banded LSH index (MinHashIndex, SimHashIndex, MinHashStringIndex) for sub-linear near-duplicate lookups
• A lock-free, multi-threaded clustering algorithm built on rayon and atomic pointers
• Python bindings (pip install gaoya) exposing the same indexes and clustering from Python

Common Use Cases

• Deduplicating large text corpora (e.g. scraped web pages, scholarly articles) before training or indexing
• Near-duplicate detection in search and crawling pipelines
• Clustering documents by textual similarity without full pairwise comparison
• Fuzzy record matching and entity resolution over free-text fields

Under The Hood

Architecture The crate is organized into four modules under gaoya/src/ — minhash, simhash, text, and clustering — each owning one layer of the pipeline. Hashing lives in min_hasher.rs/min_hasher64.rs/super_min_hash.rs and sim_hash.rs, generated largely through a make_min_hasher! macro that produces signature types over a BuildHasher. Signatures feed banded index structures (MinHashIndex, SimHashIndex, MinHashStringIndex) that group signature bands into MinHashBands keyed by a custom BandKey/NoOpHasher pair, avoiding redundant re-hashing of already-hashed band contents. The clustering module builds on top of the index through a QueryIndex trait, assigning documents to clusters with AtomicPtr compare-exchange operations rather than locks. The layers are cleanly separated, but genuinely coupled through shared generics (MinHashType, IdContainer), so a change to the core similarity computation would ripple through indexing and clustering alike.

Tech Stack Rust (2024 edition), organized as a Cargo workspace with two members: the gaoya core crate and py-gaoya, a PyO3 binding crate built with maturin into abi3 wheels compatible across Python 3.9–3.13. Dependencies include rayon for data-parallel indexing and clustering, several interchangeable hashing backends (ahash, siphasher, seahash, fnv), and low-allocation concurrency primitives (smallvec, triomphe’s Arc, crossbeam-utils atomics). Benchmarks run through criterion. CI (GitHub Actions) builds and tests the Rust crate, runs a pytest matrix across five Python versions for the bindings, and builds platform wheels for release; the crate is published to crates.io and the Python package to PyPI.

Code Quality Testing uses Rust’s built-in #[cfg(test)]/#[test] convention, present across nine files in the minhash and simhash modules, plus a separate pytest suite for the Python bindings and a criterion benchmark harness. Both suites run in CI on every push and pull request. Comment density is uneven — the indexing code is thoroughly documented while several lower-level hashing and simhash files carry no doc comments — and the crate root explicitly allows dead_code and unused lints rather than enforcing a clean-warnings policy. The clustering module’s unsafe impl Send/Sync blocks around raw atomic pointers work but aren’t accompanied by extensive safety documentation.

API Design The public API centers on a handful of concrete types — MinHasher32/MinHasher64, MinHashIndex, SimHashIndex, MinHashStringIndex — with a consistent create_signature / insert / query shape across both minhash and simhash paths, so switching signature schemes doesn’t require restructuring caller code. MinHashStringIndex in particular lowers the barrier for text-only use cases by handling tokenization and casing internally rather than requiring callers to pre-shingle text. Documentation leans on runnable doc-tests in lib.rs and parallel Rust/Python README examples rather than a dedicated docs site, which is adequate for a focused library but requires reading source to go beyond the basics.