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

MINHASH_LSH
Private Preview

効率的な重複除去と類似性検索は、大規模機械学習データセット、特に大規模言語モデル（LLM）の学習コーパスのクリーニングなどのタスクにとって重要です。数百万または数十億のドキュメントを扱う場合、従来の完全一致検索は遅くなりすぎてコストが高くなります。

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

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

  • 局所性鋭感ハッシュ（LSH）: MinHash署名に基づいて類似ドキュメントのグループを迅速に検索します。

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

概要​

ジャッカード類似度​

ジャッカード類似度は、2つの集合AとBの重複を測定し、正式には次のように定義されます。

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

その値の範囲は0（完全に重複なし）から1（完全一致）です。

しかし、大規模データセット内のすべてのドキュメントペア間でジャッカード類似度を正確に計算することは計算量が多くなります。nが大きい場合、時間とメモリが**O(n²)**になります。これは、LLMの学習コーパスのクリーニングやウェブ規模のドキュメント分析などのユースケースでは現実的ではありません。

MinHash署名: 近似ジャッカード類似度​

MinHashはジャッカード類似度を推定するための効率的な方法を提供する確率的技術です。これは、各集合をコンパクトな署名ベクトルに変換して、集合類似性を効率的に近似するために十分な情報を保存します。

核心的なアイデア:

2つの集合がより似ているほど、それらのMinHash署名が同じ位置で一致する可能性が高くなります。この性質により、MinHashは集合間のジャッカード類似度を近似できます。

この性質により、MinHashは集合を直接比較する必要なく集合間のジャッカード類似度を近似できます。

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

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

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

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

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

CCzEwT7uchMqI6bsxRJcK1qenEh

📘注意

使用するハッシュ関数の数は、MinHash署名の次元数を決定します。より高次元により良い近似精度が得られますが、ストレージと計算量が増加します。

MinHashのためのLSH​

MinHash署名はドキュメント間の正確なジャッカード類似度計算のコストを大幅に削減しますが、すべての署名ベクトルペアを網羅的に比較するのはスケール時にまだ効率的ではありません。

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

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

  1. 署名セグメンテーション:

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

    例として、128次元のMinHash署名（n = 128）があり、32個のバンド（b = 32）に分割する場合、各バンドには4つのハッシュ値（r = 4）が含まれます。

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

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

  3. 候補選択:

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

📘注意

なぜ効果的なのか？

数式的には、2つの署名がジャッカード類似度ssの場合、

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

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

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

詳細については、局所性鋭感ハッシュを参照してください。

128次元MinHash署名を持つ3つのドキュメントを考えてみましょう。

E1dewMnqshua0ib7aHmcL10lnIe

まず、LSHは128次元署名を各4つの連続値からなる32個のバンドに分割します。

PhSMwS74rh25oybv9Docmfionze

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

RfmMwNkIvhlUFSb11alcP8fqnmf

📘注意

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

MHJACCARD: MinHash署名の比較​

MinHash署名は固定長バイナリベクトルを使用して集合間のジャッカード類似度を近似します。しかし、これらの署名は元の集合を保持していないため、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署名を生成する必要があります。これらのコンパクトなバイナリ署名は集合間のジャッカード類似度を近似し、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()  # 2048バイトを返します

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

デフォルトでは、Zilliz Cloudは近似近隣を検索するためにMinHash署名とLSHインデックスのみを使用します。これは高速ですが、誤検知を返すか近い一致を見逃す可能性があります。

正確なジャッカード類似度が必要な場合、Zilliz Cloudは元のトークン集合を使用した精度向上検索をサポートしています。これを有効にするには：

トークン集合抽出例:

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

MinHash LSHの使用​

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

クラスタへの接続​

from pymilvus import MilvusClient

client = MilvusClient(uri="YOUR_CLUSTER_ENDPOINT")  # ご使用のURIが異なる場合は更新してください

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

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

  • プライマリキー

  • MinHash署名用のBINARY_VECTORフィールド

  • （精度向上検索が有効になっている場合）元のトークン集合用のVARCHARフィールド

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

from pymilvus import DataType

VECTOR_DIM = MINHASH_DIM * HASH_BIT_WIDTH  # 256 × 64 = 8192ビット

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)  # 精度向上に必要
schema.add_field("document", DataType.VARCHAR, max_length=1000)

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

ジャッカード精度向上が有効な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,  # 署名ビット幅と一致する必要があります
        "mh_lsh_band": 16,                       # バンド数（128/16 = 各バンド8ハッシュ）
        "with_raw_data": True                    # ジャッカード精度向上に必要
    }
)

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つのモードの類似性検索をサポートしています。

  • 近似検索 — ハッシュのみを使用し、高速だが確率的な結果を得るLSH。

  • 精度向上検索 — 改善された正確性のために元のトークン集合を使用してジャッカード類似度を再計算します。

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}. 類似度: {sim:.3f} | {hit['entity']['document']}")

これはZilliz Cloudに保存された元のトークン集合を使用した正確なジャッカード比較を有効にします。やや遅いですが、品質重視のタスクには推奨されます。

search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # 真のジャッカード計算を有効化
        "refine_k": 5                    # 上位5候補を精度向上
    }
}

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}. 類似度: {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

大規模データセット（>1M集合）にはメモリ使用量削減のためfalseを使用。最大検索速度が必要な小規模データセットにはtrueを使用。

with_raw_data

精度向上のためにLSHコードとともに元のMinHash署名を保存するか。

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

精度向上のために候補結果に対して正確なジャッカード類似度計算を実行するか。

true, false

高精度が必要なアプリケーション（例：重複除去）にはtrueを使用。わずかな精度の喪失が許容できる場合の高速近似検索にはfalseを使用。

refine_k

ジャッカード精度向上前に取得する候補数。mh_search_with_jaccardがtrueの場合にのみ有効。

[top_k, top_k * 10]

良い再現率とパフォーマンスのバランスのためには、目的のtop_kの2-5倍に設定してください。高い値は再現率を向上させますが計算コストが増加します。

mh_lsh_batch_search

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

true, false

複数クエリの同時検索でより良いスループットを求める場合はtrueを使用。メモリオーバーヘッドを削減するための単一クエリシナリオにはfalseを使用。