MINHASH_LSH

Una deduplicazione e una ricerca di similarità efficienti sono fondamentali per i dataset di apprendimento automatico su larga scala, in particolare per compiti come la pulizia dei corpora di addestramento per i modelli linguistici di grandi dimensioni (LLM). Quando si ha a che fare con milioni o miliardi di documenti, la tradizionale corrispondenza esatta diventa troppo lenta e costosa.

L'indice MINHASH_LSH di Milvus consente una deduplicazione approssimativa veloce, scalabile e precisa, combinando due potenti tecniche:

• MinHash: Genera rapidamente firme compatte (o "impronte digitali") per stimare la somiglianza dei documenti.

• Locality-Sensitive Hashing (LSH): Individua rapidamente gruppi di documenti simili in base alle loro firme MinHash.

Questa guida illustra i concetti, i prerequisiti, la configurazione e le migliori pratiche per l'utilizzo di MINHASH_LSH in Milvus.

Panoramica

Somiglianza di Jaccard

La somiglianza di Jaccard misura la sovrapposizione tra due insiemi A e B, formalmente definita come:

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

Dove il suo valore va da 0 (completamente disgiunto) a 1 (identico).

Tuttavia, calcolare esattamente la somiglianza di Jaccard tra tutte le coppie di documenti in insiemi di dati su larga scala è computazionalmente costoso-O(n²) in termini di tempo e memoria quando n è grande. Ciò lo rende impraticabile per casi d'uso come la pulizia del corpus di addestramento LLM o l'analisi dei documenti su scala web.

Firme MinHash: Similitudine di Jaccard approssimata

MinHash è una tecnica probabilistica che offre un modo efficiente per stimare la somiglianza di Jaccard. Funziona trasformando ogni insieme in un vettore di firme compatto, che conserva informazioni sufficienti per approssimare in modo efficiente la somiglianza degli insiemi.

L'idea di base:

Quanto più simili sono i due insiemi, tanto più è probabile che le loro firme MinHash corrispondano nelle stesse posizioni. Questa proprietà consente a MinHash di approssimare la somiglianza di Jaccard tra gli insiemi.

Questa proprietà consente a MinHash di approssimare la somiglianza di Jaccard tra gli insiemi senza dover confrontare direttamente gli insiemi completi.

Il processo di MinHash prevede:

1. Shingling: Convertire i documenti in insiemi di sequenze di token sovrapposte (shingle).

2. Hashing: applicazione di più funzioni hash indipendenti a ogni shingle

3. Selezione Min: Per ogni funzione hash, registrare il valore hash minimo tra tutti gli shingle.

L'intero processo è illustrato di seguito:

Flusso di lavoro Minhash

LSH per MinHash

Sebbene le firme MinHash riducano significativamente il costo del calcolo della somiglianza esatta di Jaccard tra i documenti, il confronto esaustivo di ogni coppia di vettori di firma è ancora inefficiente su scala.

Per risolvere questo problema, viene utilizzato LSH. LSH consente una rapida ricerca approssimativa della somiglianza, garantendo che gli elementi simili siano inseriti nello stesso "bucket" con alta probabilità, evitando di confrontare direttamente ogni coppia.

Il processo prevede:

1. Segmentazione della firma:

   Una firma MinHash n-dimensionale viene suddivisa in b b ande. Ogni banda contiene r valori hash consecutivi, quindi la lunghezza totale della firma soddisfa: n = b × r.

   Ad esempio, se si dispone di una firma MinHash a 128 dimensioni(n = 128) e la si divide in 32 bande(b = 32), ogni banda contiene 4 valori hash(r = 4).

2. Hashing a livello di banda:

   Dopo la segmentazione, ogni banda viene elaborata in modo indipendente utilizzando una funzione hash standard per assegnarla a un bucket. Se due firme producono lo stesso valore hash all'interno di una banda, cioè rientrano nello stesso bucket, sono considerate potenziali corrispondenze.

3. Selezione dei candidati:

   Le coppie che si scontrano in almeno una banda vengono selezionate come candidati alla somiglianza.

Consideriamo tre documenti con firme MinHash a 128 dimensioni:

Flusso di lavoro Lsh 1

Per prima cosa, LSH divide la firma a 128 dimensioni in 32 bande di 4 valori consecutivi ciascuna:

Flusso di lavoro Lsh 2

Quindi, ogni banda viene sottoposta a hashing in diversi bucket utilizzando una funzione di hash. Le coppie di documenti che condividono i bucket vengono selezionate come candidati alla somiglianza. Nell'esempio seguente, il documento A e il documento B vengono selezionati come candidati alla somiglianza, poiché i loro risultati hash si scontrano nella banda 0:

Flusso di lavoro Lsh 3

MHJACCARD: Confronto delle firme MinHash

Le firme MinHash approssimano la somiglianza di Jaccard tra gli insiemi utilizzando vettori binari a lunghezza fissa. Tuttavia, poiché queste firme non conservano gli insiemi originali, non è possibile applicare direttamente metriche standard come JACCARD, L2, o COSINE per confrontarle.

Per ovviare a questo problema, Milvus introduce un tipo di metrica specializzata, chiamata MHJACCARD, progettata appositamente per confrontare le firme MinHash.

Quando si usa MinHash in Milvus:

• Il campo vettoriale deve essere di tipo BINARY_VECTOR

• index_type deve essere MINHASH_LSH (o BIN_FLAT).

• metric_type deve essere impostato su MHJACCARD

L'uso di altre metriche non sarà valido o darà risultati errati.

Per ulteriori informazioni su questo tipo di metrica, consultare MHJACCARD.

Flusso di lavoro della deduplicazione

Il processo di deduplicazione basato su MinHash LSH consente a Milvus di identificare e filtrare in modo efficiente i record di testo o strutturati quasi duplicati prima di inserirli nella raccolta.

1. Suddivisione e pre-elaborazione: Suddivisione dei dati testuali o strutturati in arrivo (ad esempio, record, campi) in pezzi; normalizzazione del testo (eliminazione delle minuscole e della punteggiatura) e rimozione delle stopword, se necessario.

2. Costruzione delle caratteristiche: Costruire l'insieme di token utilizzati per MinHash (ad esempio, shingle dal testo; token di campo concatenati per i dati strutturati).

3. Generazione della firma MinHash: Calcolo delle firme MinHash per ogni chunk o record.

4. Conversione del vettore binario: Converte la firma in un vettore binario compatibile con Milvus.

5. Ricerca prima dell'inserimento: Utilizza l'indice MinHash LSH per cercare nella collezione di destinazione i quasi duplicati dell'elemento in arrivo.

6. Inserisci e archivia: Inserisce nella collezione solo elementi unici. Questi diventano ricercabili per i futuri controlli di dedup.

Prerequisiti

Prima di utilizzare MinHash LSH in Milvus, è necessario generare le firme MinHash. Queste firme binarie compatte approssimano la somiglianza di Jaccard tra gli insiemi e sono necessarie per la ricerca basata su MHJACCARD in Milvus.

Scegliere un metodo per generare le firme MinHash

A seconda del carico di lavoro, è possibile scegliere:

• Usare il metodo Python datasketch per semplicità (consigliato per la prototipazione)

• Utilizzare strumenti distribuiti (ad esempio, Spark, Ray) per insiemi di dati su larga scala.

• Implementare una logica personalizzata (NumPy, C++, ecc.) se la messa a punto delle prestazioni è fondamentale.

In questa guida, utilizziamo datasketch per semplicità e compatibilità con il formato di input di Milvus.

Installare le librerie necessarie

Installare i pacchetti necessari per questo esempio:

pip install pymilvus datasketch numpy

Generare le firme MinHash

Genereremo firme MinHash a 256 dimensioni, con ogni valore hash rappresentato come un intero a 64 bit. Ciò corrisponde al formato vettoriale previsto per 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

Ogni firma è 256 × 64 bit = 2048 byte. Questa stringa di byte può essere inserita direttamente in un campo BINARY_VECTOR. Per ulteriori informazioni sui vettori binari utilizzati in Milvus, consultare Vettore binario.

(Facoltativo) Preparare set di token grezzi (per la ricerca raffinata)

Per impostazione predefinita, Milvus utilizza solo le firme MinHash e l'indice LSH per trovare i vicini approssimativi. Questo metodo è veloce, ma può restituire falsi positivi o perdere corrispondenze strette.

Se si desidera una somiglianza Jaccard accurata, Milvus supporta una ricerca raffinata che utilizza i set di token originali. Per abilitarla:

• Memorizzare gli insiemi di token come campo separato VARCHAR.

• Impostare "with_raw_data": True quando si costruiscono i parametri dell'indice

• E abilitare "mh_search_with_jaccard": True quando si esegue la ricerca per similarità

Esempio di estrazione di set di token:

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

Utilizzare MinHash LSH

Una volta che i vettori MinHash e gli insiemi di token originali sono pronti, è possibile memorizzarli, indicizzarli e ricercarli utilizzando Milvus con MINHASH_LSH.

Connettersi al cluster

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Definire lo schema della raccolta

Definire uno schema con:

• La chiave primaria

• Un campo BINARY_VECTOR per le firme MinHash

• Un campo VARCHAR per l'insieme di token originali (se la ricerca raffinata è abilitata)

• Facoltativamente, un campo document per il testo originale

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

Costruire i parametri dell'indice e creare la raccolta

Costruire un indice MINHASH_LSH con il raffinamento di Jaccard abilitato:

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

Per ulteriori informazioni sui parametri di costruzione dell'indice, consultare la sezione Parametri di costruzione dell'indice.

Inserire i dati

Per ogni documento, preparare

• Una firma MinHash binaria

• Una stringa serializzata di set di token

• (facoltativamente) il testo originale

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

Eseguire la ricerca di somiglianza

Milvus supporta due modalità di ricerca della somiglianza utilizzando MinHash LSH:

• Ricerca approssimativa - utilizza solo le firme MinHash e LSH per ottenere risultati veloci ma probabilistici.

• Ricerca raffinata - ricompone la somiglianza di Jaccard utilizzando i set di token originali per una maggiore precisione.

5.1 Preparare la query

Per eseguire una ricerca di similarità, si deve generare una firma MinHash per il documento da interrogare. Questa firma deve corrispondere alla stessa dimensione e allo stesso formato di codifica utilizzati durante l'inserimento dei dati.

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

// java

// nodejs

// go

# restful

5.2 Ricerca approssimativa (solo LSH)

È veloce e scalabile, ma può mancare le corrispondenze strette o includere falsi positivi:

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 Ricerca raffinata (consigliata per la precisione):

Consente un confronto Jaccard accurato utilizzando i set di token originali memorizzati in Milvus. È leggermente più lenta, ma è consigliata per le attività sensibili alla qualità:

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

Parametri dell'indice

Questa sezione fornisce una panoramica dei parametri utilizzati per la costruzione di un indice e per l'esecuzione di ricerche sull'indice.

Parametri di costruzione dell'indice

La tabella seguente elenca i parametri che possono essere configurati in params quando si costruisce un indice.

Parametro	Descrizione	Valore Intervallo	Suggerimento per la messa a punto
mh_element_bit_width	Larghezza di bit di ciascun valore hash nella firma MinHash. Deve essere divisibile per 8.	8, 16, 32, 64	Utilizzare 32 per ottenere prestazioni e precisione equilibrate. Utilizzare 64 per una maggiore precisione con insiemi di dati più grandi. Utilizzare 16 per risparmiare memoria con una perdita di precisione accettabile.
mh_lsh_band	Numero di bande per dividere la firma MinHash per LSH. Controlla il compromesso richiamo-prestazioni.	[1, signature_length]	Per firme a 128 dim: iniziare con 32 bande (4 valori/ banda). Aumentare a 64 per un richiamo maggiore, diminuire a 16 per prestazioni migliori. Deve dividere la lunghezza della firma in modo uniforme.
mh_lsh_code_in_mem	Se memorizzare i codici hash LSH nella memoria anonima (true) o usare la mappatura della memoria (false).	vero, falso	Utilizzare false per insiemi di dati di grandi dimensioni (>1M di set) per ridurre l'uso della memoria. Usare true per insiemi di dati più piccoli che richiedono la massima velocità di ricerca.
with_raw_data	Se memorizzare le firme MinHash originali insieme ai codici LSH per il perfezionamento.	vero, falso	Usare true quando è richiesta un'alta precisione e il costo di memorizzazione è accettabile. Utilizzare false per ridurre al minimo i costi di archiviazione con una leggera riduzione della precisione.
mh_lsh_bloom_false_positive_prob	Probabilità di falsi positivi per il filtro Bloom usato nell'ottimizzazione dei bucket LSH.	[0.001, 0.1]	Utilizzare 0.01 per bilanciare l'uso della memoria e l'accuratezza. Valori più bassi (0.001) riducono i falsi positivi ma aumentano la memoria. Valori più alti (0.05) risparmiano memoria ma possono ridurre la precisione.

Parametri di ricerca specifici per l'indice

La tabella seguente elenca i parametri che possono essere configurati in search_params.params durante la ricerca sull'indice.

Parametro	Descrizione	Intervallo di valori	Suggerimento per la messa a punto
mh_search_with_jaccard	Eseguire o meno il calcolo esatto della somiglianza di Jaccard sui risultati candidati per il raffinamento.	vero, falso	Utilizzare true per le applicazioni che richiedono un'elevata precisione (ad esempio, la deduplicazione). Usare false per una ricerca approssimativa più veloce, quando è accettabile una leggera perdita di precisione.
refine_k	Numero di candidati da recuperare prima del perfezionamento di Jaccard. Efficace solo quando mh_search_with_jaccard è true.	[top_k, *top_k * 10*]	Impostare a 2-5 volte il top_k desiderato per ottenere un buon equilibrio tra richiamo e prestazioni. Valori più alti migliorano il richiamo ma aumentano il costo di calcolo.
mh_lsh_batch_search	Se abilitare l'ottimizzazione batch per più query simultanee.	vero, falso	Usare true quando si effettuano ricerche con più query simultanee per migliorare il throughput. Usare false per scenari a query singola per ridurre il carico di memoria.