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

MINHASH_LSH

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

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

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

  • ローカリティセンシティブハッシング (LSH)：MinHash署名に基づいて類似ドキュメントのグループを迅速に検出します。

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

概要​

Jaccard類似度​

Jaccard類似度は、2つの集合AとBの重なりを測定し、形式的には以下のように定義されます：

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

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

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

MinHash署名：近似Jaccard類似度​

MinHashは、Jaccard類似度を推定する効率的な方法を提供する確率的手法です。各集合をコンパクトな署名ベクトルに変換し、集合の類似性を効率的に近似するのに十分な情報を保持します。

核となる考え：

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

この性質により、MinHashは集合間のJaccard類似度を近似し、集合全体を直接比較する必要がなくなります。

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

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

  2. ハッシング：各シングルに複数の独立したハッシュ関数を適用

  3. 最小値選択：各ハッシュ関数について、すべてのシングルにわたる最小ハッシュ値を記録

以下に全プロセスを図示しています。

CCzEwT7uchMqI6bsxRJcK1qenEh

📘備考

使用するハッシュ関数の数は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つの帯で衝突するペアが類似候補として選択されます。

📘備考

なぜこれで機能するのか？

数学的に、2つの署名がJaccard類似度ssを持つ場合、

  • ある行（ハッシュ位置）で同一である確率は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類似度を近似します。ただし、これらの署名は元の集合を保持しないため、JACCARD、L2、COSINEなどの標準メトリックを直接比較に使用することはできません。

これを解決するために、Zilliz CloudはMHJACCARDと呼ばれる特殊なメトリックタイプを導入し、MinHash署名の比較に特化して設計されています。

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()  # 2048バイトを返す

各署名は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ベクトルと元のトークンセットの準備ができれば、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)

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

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,  # 署名ビット幅と一致する必要があります
        "mh_lsh_band": 16,                       # 帯数（128/16 = 各帯8ハッシュ）
        "with_raw_data": True                    # Jaccard精製に必要
    }
)

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

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

search_params = {
    "metric_type": "MHJACCARD",
    "params": {
        "mh_search_with_jaccard": True,  # 実際のJaccard計算を有効化
        "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, 署名長]

128次元署名の場合：32帯（各帯4値）から始めてください。再現率を高めるには64に増やし、パフォーマンスを向上させるには16に減らしてください。署名長を均等に分割する必要があります。

mh_lsh_code_in_mem

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

true, false

大規模データセット（>100万セット）ではメモリ使用量を削減するために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

精製のために候補結果上で正確な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を使用。