MINHASH_LSH

La déduplication et la recherche de similarités efficaces sont essentielles pour les ensembles de données d'apprentissage automatique à grande échelle, en particulier pour les tâches telles que le nettoyage des corpus d'entraînement pour les grands modèles de langage (LLM). Lorsqu'il s'agit de millions ou de milliards de documents, la correspondance exacte traditionnelle devient trop lente et trop coûteuse.

L'index MINHASH_LSH de Milvus permet une déduplication approximative rapide, évolutive et précise en combinant deux techniques puissantes :

• MinHash: Génère rapidement des signatures compactes (ou "empreintes digitales") pour estimer la similarité des documents.

• Hachage sensible à la localité (LSH) : Permet de trouver rapidement des groupes de documents similaires sur la base de leurs signatures MinHash.

Ce guide présente les concepts, les conditions préalables, la configuration et les meilleures pratiques pour l'utilisation de MINHASH_LSH dans Milvus.

Vue d'ensemble

Similitude de Jaccard

La similarité de Jaccard mesure le chevauchement entre deux ensembles A et B, formellement défini comme suit :

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

Sa valeur est comprise entre 0 (complètement disjoint) et 1 (identique).

Cependant, le calcul exact de la similarité de Jaccard entre toutes les paires de documents dans les ensembles de données à grande échelle est coûteux en temps et en mémoire (O(n²)) lorsque n est grand. Cela le rend infaisable pour des cas d'utilisation tels que le nettoyage de corpus de formation LLM ou l'analyse de documents à l'échelle du web.

Signatures MinHash : Similitude approximative de Jaccard

MinHash est une technique probabiliste qui offre un moyen efficace d'estimer la similarité de Jaccard. Elle transforme chaque ensemble en un vecteur de signature compact, préservant suffisamment d'informations pour estimer efficacement la similarité des ensembles.

L'idée de base:

Plus les deux ensembles sont similaires, plus leurs signatures MinHash sont susceptibles de correspondre aux mêmes positions. Cette propriété permet à MinHash d'approximer la similarité de Jaccard entre les ensembles.

Cette propriété permet à MinHash de calculer approximativement la similarité de Jaccard entre les ensembles sans qu'il soit nécessaire de comparer directement les ensembles complets.

Le processus MinHash implique

1. Le shingling: Convertir les documents en ensembles de séquences de jetons qui se chevauchent (shingles).

2. Hachage: application de plusieurs fonctions de hachage indépendantes à chaque shingle

3. Sélection Min : Pour chaque fonction de hachage, enregistrer la valeur de hachage minimale pour tous les shingles.

L'ensemble du processus est illustré ci-dessous :

Flux de travail Minhash

LSH pour MinHash

Bien que les signatures MinHash réduisent considérablement le coût du calcul de la similarité Jaccard exacte entre les documents, la comparaison exhaustive de chaque paire de vecteurs de signature reste inefficace à grande échelle.

Pour résoudre ce problème, LSH est utilisé. LSH permet une recherche de similarité approximative rapide en garantissant que les éléments similaires sont hachés dans le même "seau" avec une forte probabilité - évitant ainsi la nécessité de comparer chaque paire directement.

Le processus comprend

1. Segmentation de la signature :

   Une signature MinHash à n dimensions est divisée en b bandes. Chaque bande contient r valeurs de hachage consécutives, de sorte que la longueur totale de la signature est égale à : n = b × r.

   Par exemple, si vous avez une signature MinHash à 128 dimensions(n = 128) et que vous la divisez en 32 bandes(b = 32), chaque bande contient 4 valeurs de hachage(r = 4).

2. Hachage au niveau de la bande :

   Après la segmentation, chaque bande est traitée indépendamment à l'aide d'une fonction de hachage standard afin de l'affecter à un panier. Si deux signatures produisent la même valeur de hachage dans une bande - c'est-à-dire qu'elles appartiennent au même panier -, elles sont considérées comme des correspondances potentielles.

3. Sélection des candidats :

   Les paires qui entrent en conflit dans au moins une bande sont sélectionnées en tant que candidats à la similarité.

Considérons trois documents avec des signatures MinHash à 128 dimensions :

Flux de travail Lsh 1

Tout d'abord, LSH divise la signature à 128 dimensions en 32 bandes de 4 valeurs consécutives chacune :

Lsh Workflow 2

Ensuite, chaque bande est hachée en différents groupes à l'aide d'une fonction de hachage. Les paires de documents partageant les mêmes groupes sont sélectionnées comme candidats à la similarité. Dans l'exemple ci-dessous, le document A et le document B sont sélectionnés comme candidats à la similarité, car leurs résultats de hachage coïncident dans la bande 0:

Flux de travail Lsh 3

MHJACCARD : Comparaison des signatures MinHash

Les signatures MinHash représentent une approximation de la similarité de Jaccard entre des ensembles à l'aide de vecteurs binaires de longueur fixe. Toutefois, étant donné que ces signatures ne préservent pas les ensembles d'origine, les mesures standard telles que JACCARD, L2 ou COSINE ne peuvent pas être appliquées directement pour les comparer.

Pour y remédier, Milvus introduit un type de mesure spécialisé appelé MHJACCARD, conçu spécifiquement pour comparer les signatures MinHash.

Lors de l'utilisation de MinHash dans Milvus :

• Le champ vectoriel doit être de type BINARY_VECTOR

• L'adresse index_type doit être MINHASH_LSH (ou BIN_FLAT).

• Le champ metric_type doit être défini sur MHJACCARD

L'utilisation d'autres métriques ne sera pas valide ou donnera des résultats incorrects.

Pour plus d'informations sur ce type de métrique, voir MHJACCARD.

Flux de travail de la déduplication

Le processus de déduplication optimisé par MinHash LSH permet à Milvus d'identifier et de filtrer efficacement les enregistrements textuels ou structurés presque en double avant de les insérer dans la collection.

1. Découpage et prétraitement: Diviser les données textuelles entrantes ou les données structurées (par exemple, les enregistrements, les champs) en morceaux ; normaliser le texte (minuscules, suppression de la ponctuation) et supprimer les mots d'arrêt si nécessaire.

2. Construction des caractéristiques: Construire l'ensemble de jetons utilisé pour MinHash (par exemple, des bardeaux à partir du texte ; des jetons de champs concaténés pour les données structurées).

3. Génération de signatures MinHash: Calculer les signatures MinHash pour chaque morceau ou enregistrement.

4. Conversion en vecteur binaire: Conversion de la signature en un vecteur binaire compatible avec Milvus.

5. Recherche avant insertion: Utiliser l'index MinHash LSH pour rechercher dans la collection cible des doublons proches de l'élément entrant.

6. Insérer et stocker: Insérer uniquement des éléments uniques dans la collection. Ils deviennent consultables pour les futurs contrôles de déduplication.

Conditions préalables

Avant d'utiliser MinHash LSH dans Milvus, vous devez d'abord générer des signatures MinHash. Ces signatures binaires compactes représentent approximativement la similarité Jaccard entre les ensembles et sont nécessaires pour la recherche basée sur MHJACCARD dans Milvus.

Choisir une méthode pour générer des signatures MinHash

En fonction de votre charge de travail, vous pouvez choisir :

• Utiliser la méthode Python datasketch de Python pour plus de simplicité (recommandé pour le prototypage)

• Utiliser des outils distribués (par exemple, Spark, Ray) pour les ensembles de données à grande échelle.

• Mettre en œuvre une logique personnalisée (NumPy, C++, etc.) si l'optimisation des performances est essentielle.

Dans ce guide, nous utilisons datasketch pour des raisons de simplicité et de compatibilité avec le format d'entrée Milvus.

Installer les bibliothèques nécessaires

Installez les paquets nécessaires pour cet exemple :

pip install pymilvus datasketch numpy

Générer des signatures MinHash

Nous allons générer des signatures MinHash à 256 dimensions, chaque valeur de hachage étant représentée par un entier de 64 bits. Cela correspond au format vectoriel attendu pour 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

Chaque signature est composée de 256 × 64 bits = 2048 octets. Cette chaîne d'octets peut être directement insérée dans un champ BINARY_VECTOR. Pour plus d'informations sur les vecteurs binaires utilisés dans Milvus, voir Vecteur binaire.

(Facultatif) Préparer des ensembles de jetons bruts (pour une recherche affinée)

Par défaut, Milvus utilise uniquement les signatures MinHash et l'index LSH pour trouver des voisins approximatifs. Cette méthode est rapide mais peut renvoyer des faux positifs ou manquer des correspondances proches.

Si vous souhaitez obtenir une similarité Jaccard précise, Milvus prend en charge la recherche affinée qui utilise les ensembles de jetons originaux. Pour l'activer :

• Stocker les jeux de jetons dans un champ VARCHAR distinct.

• Définir "with_raw_data": True lors de l'élaboration des paramètres de l'index

• Et activer "mh_search_with_jaccard": True lors de la recherche de similarité

Exemple d'extraction d'un jeu de jetons:

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

Utiliser MinHash LSH

Une fois que vos vecteurs MinHash et vos ensembles de jetons originaux sont prêts, vous pouvez les stocker, les indexer et les rechercher à l'aide de Milvus avec MINHASH_LSH.

Connectez-vous à votre cluster

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Définir le schéma de la collection

Définissez un schéma avec :

• La clé primaire

• Un champ BINARY_VECTOR pour les signatures MinHash

• Un champ VARCHAR pour le jeu de jetons original (si la recherche affinée est activée)

• Optionnellement, un champ document pour le texte original

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

Construire les paramètres de l'index et créer la collection

Construire un index MINHASH_LSH avec le raffinement Jaccard activé :

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

Pour plus d'informations sur les paramètres de construction de l'index, voir Paramètres de construction de l'index.

Insérer des données

Pour chaque document, préparez

• une signature MinHash binaire

• Une chaîne de jetons sérialisée

• (optionnellement) le texte original

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

Effectuer une recherche de similarité

Milvus prend en charge deux modes de recherche de similarités à l'aide de MinHash LSH :

• Recherche approximative - utilise uniquement les signatures MinHash et LSH pour des résultats rapides mais probabilistes.

• Recherche affinée - recalcule la similarité de Jaccard à l'aide des ensembles de jetons d'origine pour une meilleure précision.

5.1 Préparation de la requête

Pour effectuer une recherche de similarité, il faut générer une signature MinHash pour le document de la requête. Cette signature doit correspondre à la même dimension et au même format d'encodage que ceux utilisés lors de l'insertion des données.

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

// java

// nodejs

// go

# restful

5.2 Recherche approximative (LSH uniquement)

Cette méthode est rapide et évolutive, mais peut manquer des correspondances proches ou inclure des faux positifs :

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 Recherche affinée (recommandée pour la précision) :

Elle permet une comparaison Jaccard précise à l'aide des ensembles de jetons originaux stockés dans Milvus. Elle est légèrement plus lente mais recommandée pour les tâches sensibles à la 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

Paramètres de l'index

Cette section présente une vue d'ensemble des paramètres utilisés pour construire un index et effectuer des recherches sur l'index.

Paramètres de construction d'index

Le tableau suivant répertorie les paramètres qui peuvent être configurés sur params lors de la création d'un index.

Paramètre	Description de l'index	Plage de valeurs	Suggestion de réglage
mh_element_bit_width	Largeur de bit de chaque valeur de hachage dans la signature MinHash. Doit être divisible par 8.	8, 16, 32, 64	Utilisez 32 pour équilibrer les performances et la précision. Utilisez 64 pour une plus grande précision avec des ensembles de données plus importants. Utilisez 16 pour économiser de la mémoire avec une perte de précision acceptable.
mh_lsh_band	Nombre de bandes pour diviser la signature MinHash pour LSH. Contrôle le compromis rappel-performance.	[1, signature_length]	Pour les signatures de 128 dim : commencer avec 32 bandes (4 valeurs/bande). Augmenter à 64 pour un meilleur rappel, diminuer à 16 pour de meilleures performances. La longueur de la signature doit être divisée de manière égale.
mh_lsh_code_in_mem	Indique s'il faut stocker les codes de hachage LSH dans la mémoire anonyme (true) ou utiliser le mappage de la mémoire (false).	true, false	Utilisez false pour les grands ensembles de données (>1M sets) afin de réduire l'utilisation de la mémoire. Utilisez true pour les petits ensembles de données nécessitant une vitesse de recherche maximale.
with_raw_data	Stocker ou non les signatures MinHash originales avec les codes LSH pour l'affinage.	true, false	Utilisez true lorsqu'une grande précision est requise et que le coût de stockage est acceptable. Utiliser false pour minimiser les frais de stockage tout en réduisant légèrement la précision.
mh_lsh_bloom_false_positive_prob	Probabilité de faux positifs pour le filtre de Bloom utilisé dans l'optimisation du panier LSH.	[0.001, 0.1]	Utiliser 0.01 pour équilibrer l'utilisation de la mémoire et la précision. Les valeurs inférieures (0.001) réduisent les faux positifs mais augmentent la mémoire. Des valeurs plus élevées (0.05) économisent de la mémoire mais peuvent réduire la précision.

Paramètres de recherche spécifiques à l'index

Le tableau suivant répertorie les paramètres qui peuvent être configurés dans search_params.params lors d'une recherche sur l'index.

Paramètre	Description des paramètres	Plage de valeurs	Suggestion d'ajustement
mh_search_with_jaccard	Effectuer ou non un calcul exact de la similarité de Jaccard sur les résultats candidats à l'affinage.	true, false	Utilisez true pour les applications nécessitant une grande précision (par exemple, la déduplication). Utilisez false pour une recherche approximative plus rapide lorsqu'une légère perte de précision est acceptable.
refine_k	Nombre de candidats à récupérer avant l'affinage Jaccard. Uniquement efficace lorsque mh_search_with_jaccard est true.	[top_k, *top_k * 10*]	Fixé à 2-5x le top_k souhaité pour un bon équilibre rappel-performance. Des valeurs plus élevées améliorent le rappel mais augmentent le coût de calcul.
mh_lsh_batch_search	Permet d'activer ou non l'optimisation par lots pour plusieurs requêtes simultanées.	true, false	Utilisez true lorsque vous effectuez des recherches avec plusieurs requêtes simultanées afin d'améliorer le débit. Utilisez false pour les scénarios à requête unique afin de réduire la surcharge de mémoire.