MINHASH_LSH

効率的な重複排除と類似検索は、大規模な機械学習データセット、特に大規模言語モデル(LLM)の学習コーパスのクリーニングのようなタスクにとって重要である。数百万、数十億のドキュメントを扱う場合、従来の完全マッチングでは時間とコストがかかりすぎる。

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

• MinHash：MinHash：文書の類似性を推定するためのコンパクトなシグネチャ（または「フィンガープリント」）を素早く生成する。

• Locality-Sensitive Hashing (LSH)：MinHash署名に基づいて、類似文書のグループを迅速に検出します。

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

概要

Jaccard類似度

Jaccard類似度は2つの集合AとBの重なりを測定するもので、正式には以下のように定義される：

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

ここで、その値は0（完全に不一致）から1（同一）までである。

しかしながら、大規模なデータセットにおける全ての文書対の間でジャカード類似度を正確に計算することは、nが大きい場合、時間とメモリに計算量-O(n²)を要する。このため、LLM訓練コーパスのクリーニングやウェブスケールの文書解析のようなユースケースでは実行不可能である。

MinHash署名：近似ジャカード類似度

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

核となる考え方

2つのセットが類似しているほど、MinHash署名が同じ位置で一致する可能性が高くなります。この特性により、MinHashはセット間のJaccard類似度を近似できます。

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

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

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

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

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

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

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つのバンドで衝突するペアが類似候補として選択される。

128次元のMinHash署名を持つ3つのドキュメントを考える：

Lshワークフロー1

まず、LSHは128次元の署名を、それぞれ連続する4つの値からなる32のバンドに分割する：

Lshワークフロー2

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

Lsh ワークフロー 3

MHJACCARDを参照のこと：MinHash署名の比較

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

これに対処するため、MilvusはMinHashシグネチャを比較するために特別に設計された、MHJACCARD と呼ばれる特別なメトリックタイプを導入している。

MilvusでMinHashを使用する場合：

• ベクトルフィールドはBINARY_VECTOR

• index_type はMINHASH_LSH (またはBIN_FLAT) でなければならない。

• metric_type は必ずMHJACCARD

他のメトリックを使用すると、無効であるか、正しくない結果が得られます。

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

重複排除ワークフロー

MinHash LSHを使用した重複排除プロセスにより、Milvusはコレクションに挿入する前に、重複しそうなテキストまたは構造化レコードを効率的に識別し、フィルタリングすることができます。

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

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

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

4. バイナリベクトル変換：署名をMilvusと互換性のあるバイナリベクトルに変換します。

5. 挿入前の検索：MinHash LSHインデックスを使用して、ターゲットコレクションを検索し、入力されるアイテムの 重複に近いものを探します。

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

前提条件

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

MinHashシグネチャの生成方法の選択

作業負荷に応じて、以下の方法を選択できます：

• Pythonの datasketchを使用する（プロトタイピングに推奨）。

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

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

このガイドでは、シンプルさとMilvus入力フォーマットとの互換性のために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 フィールドに直接挿入できる。Milvusで使用されるバイナリベクタの詳細については、バイナリベクタを参照してください。

(オプション) (絞り込み検索用の)生トークンセットの準備

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

正確なJaccard類似度を求める場合、Milvusはオリジナルのトークンセットを使用した絞り込み検索をサポートしています。これを有効にするには

• トークンセットを別のVARCHAR フィールドとして保存する。

• インデックスパラメータを作成する際に"with_raw_data": True を設定する。

• また、類似検索の実行時に"mh_search_with_jaccard": True を有効にします。

トークンセット抽出の例

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

MinHash LSHの使用

MinHashベクトルとオリジナルのトークンセットの準備ができたら、Milvusを使用して、MINHASH_LSH を使用して、それらを保存、インデックス、検索することができます。

クラスタに接続

from pymilvus import MilvusClient

client = MilvusClient(uri="http://localhost:19530")  # Update if your URI is different

// java

// nodejs

// go

# restful

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

スキーマを定義する：

• 主キー

• 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)

// java

// nodejs

// go

# restful

インデックス・パラメータを構築し、コレクションを作成する

Jaccard refinement を有効にして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)

// java

// nodejs

// go

# restful

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

データの挿入

各ドキュメントについて、以下を準備する：

• バイナリ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")

// java

// nodejs

// go

# restful

類似検索の実行

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

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

• 絞り込み検索- オリジナルのトークンセットを使用してJaccard類似度を再計算し、精度を向上させます。

5.1 クエリの準備

類似性検索を実行するには、クエリ文書のMinHash署名を生成します。この署名は、データ挿入時に使用されたディメンジョンとエンコード形式と一致する必要があります。

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

// java

// nodejs

// go

# restful

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']}")

// java

// nodejs

// go

# restful

5.3 精緻化検索（精度のために推奨）：

Milvusに保存されているオリジナルのトークンセットを使って、正確な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']}")

// java

// nodejs

// go

# restful

インデックスパラメータ

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

インデックス作成パラメータ

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

パラメータ	説明	値の範囲	チューニングの提案
mh_element_bit_width	MinHash署名の各ハッシュ値のビット幅。8で割り切れる値でなければならない。	8, 16, 32, 64	パフォーマンスと精度のバランスをとるには32 。より大きなデータセットでより高い精度を得るには、64 を使用する。精度の低下を許容してメモリを節約するには、16 を使用する。
mh_lsh_band	LSHのMinHashシグネチャを分割するバンドの数。リコールと性能のトレードオフを制御する。	[1,signature_length]。	128 dimシグネチャの場合：32バンド（4値/バンド）で開始。より高い想起のためには64バンドに増やし、より良い性能のためには16バンドに減らす。署名の長さを均等に分割する必要がある。
mh_lsh_code_in_mem	LSH ハッシュ・コードを匿名メモリー (true) に格納するか、メモリー・マッピング (false) を使うか。	true, false	大規模なデータセット（>1M セット）には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 refinement の前に検索する候補の数。mh_search_with_jaccard がtrue のときのみ有効。	[top_k, *top_k * 10*]。	良好な想起-性能バランスを得るために、希望するtop_kの 2-5 倍に設定する。値を大きくすると再現率は向上するが、計算コストは増加する。
mh_lsh_batch_search	複数の同時クエリに対してバッチ最適化を有効にするかどうか。	true, false	スループットを向上させるため、複数のクエリを同時に検索する場合はtrue を使用する。メモリのオーバーヘッドを削減するために、単一クエリのシナリオではfalse を使用します。