ekzhu/datasketch

何を解決するか

非常に大きなデータセットを極めて高速に処理・検索する方法を提供します。メモリに完全なデータセットを保持・処理する必要なく、非常に大きなデータ量における類似性と基数（ユニークな要素数）を計算する問題を解決します。

動作方法

このライブラリは「スケッチ」と呼ばれる確率的データ構造を使用して、データのコンパクトな表現を作成します。データの特性を推定するための複数のアルゴリズムを実装しています：

• MinHash および Weighted MinHash：Jaccard類似度と基数を推定するために使用。
• HyperLogLog および HyperLogLog++：ユニークな要素数（基数）を推定するために使用。

これらのスケッチを効率的に検索するため、以下のようなインデックスを提供しています。これにより、線形時間より低いクエリ時間（サブ線形）を実現します：

• しきい値ベースの類似性検索に使用する局所性に敏感なハッシュ（LSH）
• カスタムメトリクスのTop-Kクエリに使用するHNSW

対象ユーザー

10億規模のデータセット上で高速な類似性検索やユニークなアイテムのカウントを必要とする、ビッグデータを扱うデータエンジニアやソフトウェア開発者。

特徴

• 確率的効率性：メモリ使用量を最小限に抑えながら、高速に大規模データを処理。
• スケーラブルなストレージ：LSHインデックス用にRedisやCassandraをストレージレイヤーとしてサポート。
• 多様なインデックス：Jaccardしきい値やTop-Kクエリなど、異なるクエリタイプに対応するLSH、LSHBloom、LSHフォレスト、HNSWを提供。
• 柔軟なスキーム：データセットのサイズに応じてメモリと速度を最適化するための複数の置換スキーム（例：affine32、affine64）を提供。