beowolx/rensa

何を解決するか

Rensaは、大規模なデータセット間の類似性を推定し、類似した重複ドキュメントを特定する高速な方法を提供します。datasketchやFastSketchといった既存のライブラリよりもはるかに高速な代替手段として設計されています。

動作方法

Rensaは、ランダムなハッシュ関数を使用してセットのコンパクトな「シグネチャ」を作成するMinHashを実装しています。2つのシグネチャ間の一致するスロットの割合が、元のセットのJaccard類似度を推定します。

Rensaは2つのバリアントを提供します：

• R-MinHash：独自のバリアントで、モジュラ減算ではなく乗算-シフトハッシュ（64ビットの乗算-加算の上位32ビットを取得）を使用し、CPUオーバーヘッドとメモリ使用量を削減します。
• C-MinHash：公式論文に基づくバリアントで、より小さなパラメータセットから複数のスロットを2段階のスキームで導出することで、より厳密な分散バウンドを実現します。

このプロジェクトはRustで書かれており、Pythonバインディングを備え、非暗号的ハッシュ、要素のバッチ処理、MiMallocアロケータの使用といった低レベル最適化を採用しています。

対象ユーザー

標準的なPython実装が遅すぎる大規模データセット上で類似性推定や重複検出を必要とするデータエンジニアやML実践者

特徴

• 極めて高速：datasketchより最大608倍高速、FastSketchより11倍高速であるとベンチマークで確認されています。
• メモリ効率良好：R-MinHashシグネチャは32ビット整数を使用し、64ビット実装と比較してメモリ要件を半分に削減します。
• LSH統合：局所性に敏感なハッシュ（LSH）を内蔵しており、すべてのペアを比較せずに効率的な候補検索が可能です。
• ストリーミング対応：継続的なデータストリーム用の組み込み重複除去機能を備えています。
• 柔軟なAPI：一括処理とインクリメンタル更新の両方をサポートしています。