メインコンテンツまでスキップ
バージョン: User Guides (Cloud)

MINHASH_LSH

大規模な機械学習データセット、特に大規模言語モデル（LLM）のトレーニングコーパスのクリーニングなどのタスクでは、効率的な重複排除と類似性検索が不可欠です。数百万または数十億のドキュメントを扱う場合、従来の厳密なマッチングは遅すぎ、コストがかかりすぎます。

Zilliz CloudのMINHASH_LSHインデックスは、2つの強力な技術を組み合わせることで、高速でスケーラブルかつ正確な近似重複排除を可能にします。

  • MinHash: ドキュメントの類似性を推定するために、コンパクトなシグネチャ（または「フィンガープリント」）を迅速に生成します。

  • Locality-Sensitive ハッシュ化 (LSH): MinHashシグネチャに基づいて、類似するドキュメントのグループを迅速に検索します。

このガイドでは、Zilliz CloudでMINHASH_LSHを使用するための概念、前提条件、セットアップ、およびベストプラクティスについて説明します。

概要​

Jaccard類似度​

Jaccard類似度は、2つの集合AとBの重なりを測定し、次のように正式に定義されます。

J(A,B)=∣A∩B∣∣A∪B∣J(A, B) = \frac{|A \cap B|}{|A \cup B|}

その値は0（完全に分離）から1（同一）の範囲です。

しかし、大規模データセット内のすべてのドキュメントペア間でJaccard類似度を正確に計算することは、計算コストが高く、nが大きい場合、時間とメモリの両方で**O(n²)**になります。このため、LLMトレーニングコーパスのクリーニングやウェブスケールのドキュメント分析などのユースケースでは、実現不可能です。

MinHashシグネチャ: Jaccard類似度の近似​

MinHashは、Jaccard類似度を推定するための効率的な方法を提供する確率的技術です。各集合をコンパクトなシグネチャベクトルに変換し、集合の類似度を効率的に近似するのに十分な情報を保持することで機能します。

核となるアイデア:

2つの集合が似ているほど、MinHashシグネチャが同じ位置で一致する可能性が高くなります。この特性により、MinHashは集合間のJaccard類似度を近似することができます。

この特性により、MinHashは完全な集合を直接比較することなく、集合間のJaccard類似度を近似することができます。

MinHashプロセスには以下が含まれます。

  1. シャイングリング: ドキュメントを重複するトークンシーケンス（シャイングリング）の集合に変換します。

  2. ハッシュ化: 各シャイングリングに複数の独立したハッシュ関数を適用します。

  3. 最小選択: 各ハッシュ関数について、すべてのシャイングリングの中で最小のハッシュ値を記録します。

プロセス全体を以下に示します。

CCzEwT7uchMqI6bsxRJcK1qenEh

📘Notes

使用されるハッシュ関数の数は、MinHashシグネチャの次元を決定します。次元が高いほど近似精度は向上しますが、ストレージと計算量が増加します。

MinHashのためのLSH​

MinHashシグネチャは、ドキュメント間の厳密なJaccard類似度を計算するコストを大幅に削減しますが、すべてのシグネチャベクトルペアを網羅的に比較することは、大規模では依然として非効率です。

これを解決するために、LSHが使用されます。LSHは、類似するアイテムが高い確率で同じ「バケット」にハッシュされるようにすることで、高速な近似類似性検索を可能にします。これにより、すべてのペアを直接比較する必要がなくなります。

プロセスには以下が含まれます。

  1. シグネチャのセグメンテーション:

    n次元のMinHashシグネチャは、b個のバンドに分割されます。各バンドにはr個の連続するハッシュ値が含まれるため、合計シグネチャ長はn = b × rを満たします。

    たとえば、128次元のMinHashシグネチャ（n = 128）があり、それを32個のバンド（b = 32）に分割する場合、各バンドには4個のハッシュ値（r = 4）が含まれます。

  2. バンドレベルのハッシュ化:

    セグメンテーション後、各バンドは標準のハッシュ関数を使用して独立して処理され、バケットに割り当てられます。2つのシグネチャがバンド内で同じハッシュ値を生成する場合、つまり同じバケットに分類される場合、それらは潜在的な一致と見なされます。

  3. 候補の選択:

    少なくとも1つのバンドで衝突するペアが類似性候補として選択されます。

📘Notes

なぜ機能するのか？

数学的に、2つのシグネチャがJaccard類似度ssを持つ場合、

  • 1つの行（ハッシュ位置）で同一である確率はssです。

  • バンドのすべてのrr行で一致する確率はsrs^rです。

  • 少なくとも1つのバンドで一致する確率は$1 - (1 - s^r)^b$です。

詳細については、Locality-sensitive hashingを参照してください。

128次元のMinHashシグネチャを持つ3つのドキュメントを考えてみましょう。

E1dewMnqshua0ib7aHmcL10lnIe

まず、LSHは128次元のシグネチャを、それぞれ4つの連続する値を持つ32個のバンドに分割します。

PhSMwS74rh25oybv9Docmfionze

次に、各バンドはハッシュ関数を使用して異なるバケットにハッシュされます。バケットを共有するドキュメントペアは、類似性候補として選択されます。以下の例では、ドキュメントAとドキュメントBは、ハッシュ結果がバンド0で衝突するため、類似性候補として選択されます。

RfmMwNkIvhlUFSb11alcP8fqnmf

📘Notes

バンドの数はmh_lsh_bandパラメータによって制御されます。詳細については、インデックス構築パラメータを参照してください。

MHJACCARD: MinHashシグネチャの比較​

MinHashシグネチャは、固定長のバイナリベクトルを使用して集合間のJaccard類似度を近似します。しかし、これらのシグネチャは元の集合を保持しないため、JACCARD、L2、COSINEなどの標準的なメトリックを直接適用して比較することはできません。

この問題に対処するため、Zilliz CloudはMinHashシグネチャの比較専用に設計されたMHJACCARDという特殊なメトリックタイプを導入しています。

Zilliz CloudでMinHashを使用する場合：

  • ベクトルフィールドはBINARY_VECTORタイプである必要があります。

  • index_typeはMINHASH_LSH（またはBIN_FLAT）である必要があります。

  • metric_typeはMHJACCARDに設定する必要があります。

他のメトリックを使用すると、無効になるか、誤った結果が生成されます。

このメトリックタイプに関する詳細については、MHJACCARDを参照してください。

重複排除ワークフロー​

MinHash LSHを搭載した重複排除プロセスにより、Zilliz Cloudは、コレクションに挿入する前に、ほぼ重複するテキストまたは構造化レコードを効率的に識別してフィルタリングできます。

NuokbSgbroyVPQx14fKcm37bnoh

  1. チャンク化と前処理: 入力テキストデータまたは構造化データ（例：レコード、フィールド）をチャンクに分割します。必要に応じてテキストを正規化（小文字化、句読点の削除）し、ストップワードを削除します。

  2. 特徴量構築: MinHashに使用するトークンセットを構築します（例：テキストからのシャイングリング、構造化データ用の連結されたフィールドトークン）。

  3. MinHashシグネチャ生成: 各チャンクまたはレコードのMinHashシグネチャを計算します。

  4. バイナリベクトル変換: シグネチャをMilvusと互換性のあるバイナリベクトルに変換します。

  5. 挿入前の検索: MinHash LSHインデックスを使用して、ターゲットコレクションで入力アイテムのほぼ重複を検索します。

  6. 挿入と保存: 一意のアイテムのみをコレクションに挿入します。これらは将来の重複排除チェックのために検索可能になります。

前提条件​

Zilliz CloudでMinHash LSHを使用する前に、まずMinHashシグネチャを生成する必要があります。これらのコンパクトなバイナリシグネチャは、集合間のJaccard類似度を近似し、Zilliz CloudでのMHJACCARDベースの検索に必要です。

MinHashシグネチャを生成する方法を選択する​

ワークロードに応じて、以下を選択できます。

  • シンプルさのためにPythonのdatasketchを使用する（プロトタイプ作成に推奨）

  • 大規模データセットには分散ツール（例：Spark、Ray）を使用する

  • パフォーマンスチューニングが重要である場合はカスタムロジック（NumPy、C++など）を実装する

このガイドでは、シンプルさとZilliz Cloud入力形式との互換性のためにdatasketchを使用します。

必要なライブラリをインストールする​

この例に必要なパッケージをインストールします。

pip install pymilvus datasketch numpy

MinHashシグネチャの生成​

256次元のMinHashシグネチャを生成します。各ハッシュ値は64ビット整数で表されます。これはMINHASH_LSHに期待されるベクトル形式と一致します。

from datasketch import MinHash
import numpy as np

MINHASH_DIM = 256
HASH_BIT_WIDTH = 64

def generate_minhash_signature(text, num_perm=MINHASH_DIM) -> bytes:
    m = MinHash(num_perm=num_perm)
    for token in text.lower().split():
        m.update(token.encode("utf8"))
    return m.hashvalues.astype('>u8').tobytes()  # Returns 2048 bytes

各シグネチャは256 × 64ビット = 2048バイトです。このバイト文字列は、BINARY_VECTORフィールドに直接挿入できます。Zilliz Cloudで使用されるバイナリベクタの詳細については、バイナリベクタを参照してください。

デフォルトでは、Zilliz CloudはMinHashシグネチャとLSHインデックスのみを使用して近似近傍を検索します。これは高速ですが、誤検知を返したり、近い一致を見逃したりする可能性があります。

正確なJaccard類似度が必要な場合、Zilliz Cloudは元のトークンセットを使用する洗練された検索をサポートしています。これを有効にするには：

トークンセット抽出の例:

def extract_token_set(text: str) -> str:
    tokens = set(text.lower().split())
    return " ".join(tokens)

MinHash LSH を使用する​

MinHash ベクトルと元のトークンセットの準備ができたら、MINHASH_LSH を使用して Zilliz Cloud でそれらを保存、インデックス作成、検索できます。

クラスターに接続する​

from pymilvus import MilvusClient

client = MilvusClient(uri="YOUR_CLUSTER_ENDPOINT")  # Update if your URI is different

コレクションスキーマの定義​

以下のスキーマを定義します。

  • プライマリキー

  • MinHashシグネチャ用のBINARY_VECTORフィールド

  • 元のトークンセット用のVARCHARフィールド（詳細検索が有効な場合）

  • オプションで、元のテキスト用のdocumentフィールド

from pymilvus import DataType

VECTOR_DIM = MINHASH_DIM * HASH_BIT_WIDTH  # 256 × 64 = 8192 bits

schema = client.create_schema(auto_id=False, enable_dynamic_field=False)
schema.add_field("doc_id", DataType.INT64, is_primary=True)
schema.add_field("minhash_signature", DataType.BINARY_VECTOR, dim=VECTOR_DIM)
schema.add_field("token_set", DataType.VARCHAR, max_length=1000)  # required for refinement
schema.add_field("document", DataType.VARCHAR, max_length=1000)

インデックスの構築パラメータとコレクションの作成​

Jaccardリファインメントを有効にしてMINHASH_LSHインデックスを構築します。

index_params = client.prepare_index_params()
index_params.add_index(
    field_name="minhash_signature",
    index_type="MINHASH_LSH",
    metric_type="MHJACCARD",
    params={
        "mh_element_bit_width": HASH_BIT_WIDTH,  # Must match signature bit width
        "mh_lsh_band": 16,                       # Band count (128/16 = 8 hashes per band)
        "with_raw_data": True                    # Required for Jaccard refinement
    }
)

client.create_collection("minhash_demo", schema=schema, index_params=index_params)

インデックス構築パラメータの詳細については、インデックス構築パラメータを参照してください。

データの挿入​

各ドキュメントについて、以下を準備します。

  • バイナリMinHashシグネチャ

  • シリアライズされたトークンセット文字列

  • (オプション) オリジナルテキスト

documents = [
    "machine learning algorithms process data automatically",
    "deep learning uses neural networks to model patterns"
]

insert_data = []
for i, doc in enumerate(documents):
    sig = generate_minhash_signature(doc)
    token_str = extract_token_set(doc)
    insert_data.append({
        "doc_id": i,
        "minhash_signature": sig,
        "token_set": token_str,
        "document": doc
    })

client.insert("minhash_demo", insert_data)
client.flush("minhash_demo")

Zilliz Cloudは、MinHash LSHを使用した類似性検索の2つのモードをサポートしています。

  • 近似検索 — MinHashシグネチャとLSHのみを使用して、高速だが確率的な結果を得ます。

  • 絞り込み検索 — 精度を向上させるために、元のトークンセットを使用してJaccard類似度を再計算します。

5.1 クエリの準備​

類似性検索を実行するには、クエリドキュメントのMinHashシグネチャを生成します。このシグネチャは、データ挿入時に使用されたものと同じ次元とエンコーディング形式に一致する必要があります。

query_text = "neural networks model patterns in data"
query_sig = generate_minhash_signature(query_text)

5.2 近似検索 (LSHのみ)​

これは高速でスケーラブルですが、近い一致を見逃したり、誤検知を含んだりする可能性があります。

search_params={
    "metric_type": "MHJACCARD", 
    "params": {}
}

approx_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(approx_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

これは、Zilliz Cloud に保存されている元のトークンセットを使用して、正確な Jaccard 比較を可能にします。若干遅くなりますが、品質が重視されるタスクには推奨されます。

search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # Enable real Jaccard computation
        "refine_k": 5                    # Refine top 5 candidates
    }
}

refined_results = client.search(
    collection_name="minhash_demo",
    data=[query_sig],
    anns_field="minhash_signature",
    search_params=search_params,
    limit=3,
    output_fields=["doc_id", "document"],
    consistency_level="Strong"
)

for i, hit in enumerate(refined_results[0]):
    sim = 1 - hit['distance']
    print(f"{i+1}. Similarity: {sim:.3f} | {hit['entity']['document']}")

インデックスパラメータ​

このセクションでは、インデックスの構築とインデックスに対する検索の実行に使用されるパラメータの概要を説明します。

インデックス構築パラメータ​

次の表は、インデックスを構築する際にparamsで設定できるパラメータを示しています。

パラメータ

説明

値の範囲

チューニングの提案

mh_element_bit_width

MinHashシグネチャ内の各ハッシュ値のビット幅。8で割り切れる必要があります。

8, 16, 32, 64

バランスの取れたパフォーマンスと精度には32を使用します。大規模なデータセットでより高い精度を得るには64を使用します。許容できる精度損失でメモリを節約するには16を使用します。

mh_lsh_band

LSHのためにMinHashシグネチャを分割するバンドの数。再現率とパフォーマンスのトレードオフを制御します。

[1, signature_length]

128次元シグネチャの場合：32バンド（4値/バンド）から始めます。再現率を高めるには64に増やし、パフォーマンスを向上させるには16に減らします。シグネチャ長を均等に分割する必要があります。

mh_lsh_code_in_mem

LSHハッシュコードを匿名メモリに保存するか（true）、メモリマッピングを使用するか（false）。

true, false

メモリ使用量を削減するために、大規模なデータセット（100万セット以上）にはfalseを使用します。最大の検索速度を必要とする小規模なデータセットにはtrueを使用します。

with_raw_data

元のMinHashシグネチャをLSHコードと一緒に保存して、洗練するかどうか。

true, false

高い精度が必要で、ストレージコストが許容できる場合はtrueを使用します。わずかな精度低下でストレージオーバーヘッドを最小限に抑えるにはfalseを使用します。

mh_lsh_bloom_false_positive_prob

LSHバケット最適化で使用されるブルームフィルタの偽陽性確率。

[0.001, 0.1]

バランスの取れたメモリ使用量と精度には0.01を使用します。低い値（0.001）は偽陽性を減らしますが、メモリを増やします。高い値（0.05）はメモリを節約しますが、精度が低下する可能性があります。

インデックス固有の検索パラメータ​

次の表は、インデックスを検索する際にsearch_params.paramsで設定できるパラメータを示しています。

パラメータ

説明

値の範囲

チューニングの提案

mh_search_with_jaccard

洗練のために候補結果に対して正確なJaccard類似度計算を実行するかどうか。

true, false

高い精度を必要とするアプリケーション（例：重複排除）にはtrueを使用します。わずかな精度損失が許容できる場合は、より高速な近似検索のためにfalseを使用します。

refine_k

Jaccard洗練の前に取得する候補の数。mh_search_with_jaccardがtrueの場合にのみ有効です。

[top_k, top_k * 10]

良好な再現率とパフォーマンスのバランスのために、目的のtop_kの2〜5倍に設定します。値が高いほど再現率は向上しますが、計算コストが増加します。

mh_lsh_batch_search

複数の同時クエリのバッチ最適化を有効にするかどうか。

true, false

スループットを向上させるために、複数のクエリを同時に検索する場合はtrueを使用します。メモリオーバーヘッドを削減するために、単一クエリのシナリオではfalseを使用します。