MINHASH_LSH

高效的重複刪除和相似性搜尋對於大規模的機器學習資料集來說是非常重要的，尤其是對於清理大型語言模型 (Large Language Models, LLM) 的訓練語料庫等任務。在處理數百萬或數十億的文件時，傳統的精確匹配會變得太慢且成本太高。

Milvus 中的MINHASH_LSH索引結合了兩種強大的技術，可實現快速、可擴充且精確的近似重複資料刪除：

• MinHash：快速產生精簡的簽名 (或「指紋」)，以估計文件的相似性。

• Locality-Sensitive Hashing (LSH)：根據 MinHash 簽署快速找到相似文件群組。

本指南將介紹在 Milvus 中使用 MINHASH_LSH 的概念、先決條件、設定和最佳實務。

概述

Jaccard 相似性

Jaccard 類似度量兩個集合 A 和 B 之間的重疊程度，正式定義為：

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

其值範圍從 0 (完全不相連) 到 1 (完全相同)。

然而，在大型資料集中精確計算所有文件對之間的 Jaccard 類似性，在時間和記憶體上的計算成本很高，當n很大時為-O(n²)。這使得它在 LLM 訓練語料清理或網路規模文件分析等使用個案中並不可行。

MinHash 簽名：近似 Jaccard 相似性

MinHash是一種概率技術，可提供估算 Jaccard 相似性的有效方法。它的工作方式是將每個集合轉換成精簡的簽章向量，保留足夠的資訊來有效率地近似集合相似性。

核心思想：

兩個集越相似，它們的 MinHash 簽署就越有可能在相同的位置匹配。這個特性讓 MinHash 可以近似集合間的 Jaccard 相似度。

這個屬性讓 MinHash 可以近似集合間的Jaccard 相似度，而不需要直接比較完整的集合。

MinHash 過程包括

1. 分組：將文件轉換為重疊標記序列 (shingles) 的集合

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. 頻段層級散列：

   分割之後，每個頻段都會使用標準散列函數獨立處理，將其分配到一個桶。如果兩個簽章在一個區段內產生相同的哈希值，也就是落入相同的桶中，則視為潛在的匹配。

3. 候選選擇：

   至少在一個頻段內碰撞的簽名對會被選為相似性候選人。

考慮三個具有 128 維 MinHash 簽署的文件：

Lsh 工作流程 1

首先，LSH 將 128 維的簽章分成 32 段，每段有 4 個連續值：

Lsh 工作流程 2

接著，使用散列函數將每個區段散列為不同的桶。共享散列的文件對會被選為相似度候選人。在下面的範例中，由於文件 A 和文件 B 的散列結果在Band 0 中相撞，因此它們被選為相似性候選項目：

Lsh 工作流程 3

MHJACCARD：比較 MinHash 簽署

MinHash 簽署使用固定長度的二進位向量來近似集合間的 Jaccard 類似性。然而，由於這些簽章不保留原始資料集，因此無法直接使用JACCARD 、L2 或COSINE 等標準度量來比較它們。

為了解決這個問題，Milvus 引進了一種稱為MHJACCARD 的特殊度量類型，專門用來比較 MinHash 簽署。

在 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++ 等)

在本指南中，我們使用datasketch 以簡化並與 Milvus 輸入格式相容。

安裝所需的函式庫

安裝本範例所需的套件：

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 向量和原始代幣集準備就緒，您就可以使用MINHASH_LSH 使用 Milvus 來儲存、索引和搜尋它們。

連接至您的集群

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

建立索引參數並建立集合

建立MINHASH_LSH 索引，並啟用 Jaccard 精細化：

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 的相似性搜尋模式：

• 近似搜尋- 只使用 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 段的簽章：從 32 段開始 (4 個值/段)。增加到 64 以獲得更高的召回率，減少到 16 以獲得更好的效能。必須平均分割簽章長度。
mh_lsh_code_in_mem	是否將 LSH 散列碼儲存於匿名記憶體 (true) 或使用記憶體映射 (false)。	true, false	對於大型資料集（>1M 組）使用false ，以減少記憶體使用量。對於需要最高搜尋速度的較小資料集，請使用true 。
with_raw_data	是否將原始 MinHash 簽署與 LSH 代碼一起儲存，以便精煉。	真、假	需要高精確度且儲存成本可接受時，使用true 。使用false ，在精確度略有降低的情況下，將儲存開銷降至最低。
mh_lsh_bloom_false_positive_prob	LSH 儲存桶最佳化中使用的 Bloom 過濾器的假陽性概率。	[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 ，以減少記憶體開銷。