beowolx/rensa

What it solves

Rensa provides a high-performance way to find near-duplicate documents in large datasets without needing to compare every single pair of documents. It solves the problem of computationally expensive deduplication by estimating Jaccard similarity using compact signatures and Locality-Sensitive Hashing (LSH).

How it works

Written in Rust with Python bindings, Rensa implements several MinHash variants:

• R-MinHash and C-MinHash: These estimate similarity based on token overlap. R-MinHash is designed for speed and produces the same signature regardless of token order or repetition.
• Rho Pipeline: A specialized pipeline that samples token positions to achieve maximum throughput for bulk filtering.
• LSH (Locality-Sensitive Hashing): This allows the library to quickly identify candidate matches, which are then checked against a similarity threshold to avoid exhaustive comparisons.
• Performance Optimizations: It uses SIMD (AVX2, AVX-512, NEON) for faster calculations, minimizes Python-to-Rust overhead, and utilizes Rayon for multi-threaded batch processing.

Who it’s for

Developers and data scientists who need to remove near-duplicate text data from large corpora, particularly those who already tokenize data in Python and require a tool that is significantly faster than existing libraries like Datasketch.

Highlights

• Extreme Speed: Benchmarked as up to 600× faster than Datasketch and 12× faster than FastSketch in batch pipelines.
• Compact Signatures: Uses 32 bits per slot, meaning a 128-slot signature takes only 512 bytes regardless of document length.
• Flexible Processing: Supports both batch processing and streaming deduplication.
• Incremental Updates: Allows sketches to be updated incrementally without needing to re-process the entire document.