MINHASH_LSH

Effiziente Deduplizierung und Ähnlichkeitssuche sind für große Datensätze des maschinellen Lernens von entscheidender Bedeutung, insbesondere für Aufgaben wie das Bereinigen von Trainingskorpora für Large Language Models (LLMs). Wenn es um Millionen oder Milliarden von Dokumenten geht, wird der herkömmliche exakte Abgleich zu langsam und kostspielig.

Der MINHASH_LSH-Index in Milvus ermöglicht eine schnelle, skalierbare und genaue annähernde Deduplizierung durch die Kombination zweier leistungsstarker Techniken:

• MinHash: Erzeugt schnell kompakte Signaturen (oder "Fingerabdrücke"), um die Ähnlichkeit von Dokumenten zu schätzen.

• Lokalitätssensitives Hashing (LSH): Findet schnell Gruppen ähnlicher Dokumente auf der Grundlage ihrer MinHash-Signaturen.

Dieser Leitfaden führt Sie durch die Konzepte, Voraussetzungen, die Einrichtung und die besten Praktiken für die Verwendung von MINHASH_LSH in Milvus.

Überblick

Jaccard-Ähnlichkeit

Die Jaccard-Ähnlichkeit misst die Überlappung zwischen zwei Mengen A und B, formal definiert als:

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

Ihr Wert reicht von 0 (völlig unzusammenhängend) bis 1 (identisch).

Die exakte Berechnung der Jaccard-Ähnlichkeit zwischen allen Dokumentenpaaren in großen Datensätzen ist jedoch sehr rechenintensiv - O(n²) in Bezug auf Zeit und Speicherplatz, wenn n groß ist. Dies macht sie für Anwendungsfälle wie die Bereinigung von LLM-Trainingskorpus oder die Analyse von Dokumenten im Web nicht praktikabel.

MinHash-Signaturen: Ungefähre Jaccard-Ähnlichkeit

MinHash ist eine probabilistische Technik, die eine effiziente Methode zur Schätzung der Jaccard-Ähnlichkeit bietet. Dabei wird jeder Satz in einen kompakten Signaturvektor umgewandelt, der genügend Informationen enthält, um die Ähnlichkeit der Sätze effizient zu approximieren.

Der Kerngedanke:

Je ähnlicher die beiden Mengen sind, desto wahrscheinlicher ist es, dass ihre MinHash-Signaturen an denselben Positionen übereinstimmen. Diese Eigenschaft ermöglicht es MinHash, die Jaccard-Ähnlichkeit zwischen Mengen zu approximieren.

Diese Eigenschaft ermöglicht es MinHash, die Jaccard-Ähnlichkeit zwischen Mengen anzunähern, ohne die vollständigen Mengen direkt vergleichen zu müssen.

Der MinHash-Prozess umfasst:

1. Shingling: Konvertierung von Dokumenten in Mengen von sich überschneidenden Token-Sequenzen (Shingles)

2. Hashing: Anwendung mehrerer unabhängiger Hash-Funktionen auf jedes Shingle

3. Min-Auswahl: Für jede Hash-Funktion wird der minimale Hash-Wert für alle Shingles ermittelt.

Der gesamte Prozess ist unten abgebildet:

Minhash Arbeitsablauf

LSH für MinHash

Während MinHash-Signaturen die Kosten für die Berechnung der exakten Jaccard-Ähnlichkeit zwischen Dokumenten erheblich reduzieren, ist der vollständige Vergleich jedes Paares von Signaturvektoren in der Größenordnung immer noch ineffizient.

Um dieses Problem zu lösen, wird LSH verwendet. LSH ermöglicht eine schnelle annähernde Ähnlichkeitssuche, indem es sicherstellt, dass ähnliche Elemente mit hoher Wahrscheinlichkeit in denselben "Bucket" gehasht werden, so dass nicht jedes Paar direkt verglichen werden muss.

Der Prozess umfasst:

1. Segmentierung der Signatur:

   Eine n-dimensionale MinHash-Signatur wird in b Bänder unterteilt. Jedes Band enthält r aufeinanderfolgende Hash-Werte, so dass die Gesamtlänge der Signatur n = b × r beträgt.

   Hat man beispielsweise eine 128-dimensionale MinHash-Signatur(n = 128) und unterteilt sie in 32 Bänder(b = 32), dann enthält jedes Band 4 Hash-Werte(r = 4).

2. Hashing auf Bandebene:

   Nach der Segmentierung wird jedes Band unabhängig mit einer Standard-Hash-Funktion verarbeitet, um es einem Bucket zuzuordnen. Wenn zwei Signaturen innerhalb eines Bandes denselben Hash-Wert ergeben, d. h. in denselben Bucket fallen, werden sie als potenzielle Übereinstimmungen betrachtet.

3. Auswahl der Kandidaten:

   Paare, die in mindestens einem Band übereinstimmen, werden als Ähnlichkeitskandidaten ausgewählt.

Betrachten Sie drei Dokumente mit 128-dimensionalen MinHash-Signaturen:

Lsh Arbeitsablauf 1

Zunächst unterteilt LSH die 128-dimensionale Signatur in 32 Bänder mit jeweils 4 aufeinanderfolgenden Werten:

Lsh Arbeitsablauf 2

Dann wird jedes Band mit Hilfe einer Hash-Funktion in verschiedene Buckets unterteilt. Dokumentenpaare, die die gleichen Buckets haben, werden als Ähnlichkeitskandidaten ausgewählt. Im folgenden Beispiel werden Dokument A und Dokument B als Ähnlichkeitskandidaten ausgewählt, da ihre Hash-Ergebnisse in Band 0 übereinstimmen:

Lsh Workflow 3

MHJACCARD: Vergleich von MinHash-Signaturen

MinHash-Signaturen approximieren die Jaccard-Ähnlichkeit zwischen Mengen durch binäre Vektoren fester Länge. Da bei diesen Signaturen jedoch die ursprünglichen Mengen nicht erhalten bleiben, können Standardmetriken wie JACCARD, L2 oder COSINE nicht direkt zum Vergleich verwendet werden.

Um dieses Problem zu lösen, führt Milvus einen speziellen Metrik-Typ namens MHJACCARD ein, der speziell für den Vergleich von MinHash-Signaturen entwickelt wurde.

Bei der Verwendung von MinHash in Milvus:

• Das Vektorfeld muss vom Typ BINARY_VECTOR

• Die index_type muss MINHASH_LSH (oder BIN_FLAT) sein.

• Der Wert metric_type muss auf MHJACCARD

Die Verwendung anderer Metriken ist entweder ungültig oder führt zu falschen Ergebnissen.

Weitere Informationen zu diesem Metrik-Typ finden Sie unter MHJACCARD.

Deduplizierungs-Workflow

Der von MinHash LSH unterstützte Deduplizierungsprozess ermöglicht es Milvus, nahezu doppelte Text- oder strukturierte Datensätze effizient zu identifizieren und herauszufiltern, bevor sie in die Sammlung eingefügt werden.

1. Chunk & Vorverarbeitung: Aufteilung eingehender Textdaten oder strukturierter Daten (z. B. Datensätze, Felder) in Chunks; Normalisierung des Textes (Kleinschreibung, Entfernung von Satzzeichen) und Entfernung von Stoppwörtern nach Bedarf.

2. Konstruktion von Merkmalen: Aufbau des für MinHash verwendeten Tokensatzes (z. B. Shingles aus Text; verkettete Feld-Token für strukturierte Daten).

3. Erzeugung von MinHash-Signaturen: Berechnen von MinHash-Signaturen für jeden Chunk oder Datensatz.

4. Binärvektor-Konvertierung: Konvertiert die Signatur in einen mit Milvus kompatiblen Binärvektor.

5. Suche vor dem Einfügen: Verwenden Sie den MinHash LSH-Index, um die Zielsammlung nach Beinahe-Duplikaten des eingehenden Elements zu durchsuchen.

6. Einfügen und speichern: Fügen Sie nur eindeutige Elemente in die Sammlung ein. Sie werden für zukünftige Dedup-Prüfungen durchsuchbar.

Voraussetzungen

Bevor Sie MinHash LSH in Milvus verwenden können, müssen Sie zunächst MinHash-Signaturen erzeugen. Diese kompakten binären Signaturen approximieren die Jaccard-Ähnlichkeit zwischen Mengen und werden für die MHJACCARD-basierte Suche in Milvus benötigt.

Wählen Sie eine Methode zur Erzeugung von MinHash-Signaturen

Abhängig von Ihrer Arbeitsbelastung können Sie wählen:

• Verwenden Sie Pythons datasketch der Einfachheit halber (empfohlen für Prototypen)

• Verwenden Sie verteilte Tools (z. B. Spark, Ray) für große Datensätze

• Implementierung benutzerdefinierter Logik (NumPy, C++ usw.), wenn die Leistungsoptimierung wichtig ist

In diesem Leitfaden verwenden wir aus Gründen der Einfachheit und Kompatibilität mit dem Milvus-Eingabeformat datasketch.

Installation der erforderlichen Bibliotheken

Installieren Sie die erforderlichen Pakete für dieses Beispiel:

pip install pymilvus datasketch numpy

Erzeugen von MinHash-Signaturen

Wir generieren 256-dimensionale MinHash-Signaturen, wobei jeder Hash-Wert als 64-Bit-Ganzzahl dargestellt wird. Dies entspricht dem erwarteten Vektorformat für 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

Jede Signatur besteht aus 256 × 64 Bit = 2048 Byte. Diese Byte-Zeichenkette kann direkt in ein BINARY_VECTOR Feld eingefügt werden. Weitere Informationen zu den in Milvus verwendeten binären Vektoren finden Sie unter Binärer Vektor.

(Optional) Roh-Token-Sets vorbereiten (für die verfeinerte Suche)

Standardmäßig verwendet Milvus nur die MinHash-Signaturen und den LSH-Index, um ungefähre Nachbarn zu finden. Dies ist schnell, kann aber falsch-positive Ergebnisse liefern oder enge Übereinstimmungen übersehen.

Wenn Sie eine genaue Jaccard-Ähnlichkeit wünschen, unterstützt Milvus eine verfeinerte Suche, die Original-Token-Sets verwendet. Um dies zu aktivieren:

• Speichern Sie Token-Sets als separates Feld VARCHAR

• Setzen Sie "with_raw_data": True bei der Erstellung von Indexparametern

• Und aktivieren Sie "mh_search_with_jaccard": True bei der Durchführung der Ähnlichkeitssuche

Beispiel für die Extraktion von Tokensätzen:

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

MinHash LSH verwenden

Sobald Ihre MinHash-Vektoren und Original-Token-Sets fertig sind, können Sie sie mit Milvus und MINHASH_LSH speichern, indizieren und durchsuchen.

Verbinden Sie sich mit Ihrem Cluster

from pymilvus import MilvusClient

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

// java

// nodejs

// go

# restful

Definieren Sie ein Sammlungsschema

Definieren Sie ein Schema mit:

• Dem Primärschlüssel

• Einem BINARY_VECTOR -Feld für die MinHash-Signaturen

• Einem VARCHAR Feld für den ursprünglichen Tokensatz (wenn die verfeinerte Suche aktiviert ist)

• Optional ein document Feld für den Originaltext

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

Index-Parameter aufbauen und Sammlung erstellen

Erstellen Sie einen MINHASH_LSH Index mit aktivierter Jaccard-Verfeinerung:

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

Weitere Informationen zu den Indexerstellungsparametern finden Sie unter Indexerstellungsparameter.

Daten einfügen

Für jedes Dokument vorbereiten:

• Eine binäre MinHash-Signatur

• Eine serialisierte Token-Set-Zeichenkette

• (Optional) den Originaltext

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

Ähnlichkeitssuche durchführen

Milvus unterstützt zwei Arten der Ähnlichkeitssuche mit MinHash LSH:

• Ungefähre Suche - verwendet nur MinHash-Signaturen und LSH für schnelle, aber probabilistische Ergebnisse.

• Verfeinerte Suche - berechnet die Jaccard-Ähnlichkeit unter Verwendung der ursprünglichen Token-Sets neu, um die Genauigkeit zu verbessern.

5.1 Vorbereiten der Abfrage

Um eine Ähnlichkeitssuche durchzuführen, erzeugen Sie eine MinHash-Signatur für das Abfragedokument. Diese Signatur muss mit der gleichen Dimension und dem gleichen Kodierungsformat übereinstimmen, das beim Einfügen der Daten verwendet wurde.

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

// java

// nodejs

// go

# restful

5.2 Näherungsweise Suche (nur LSH)

Dies ist schnell und skalierbar, kann aber enge Übereinstimmungen übersehen oder falsch positive Ergebnisse enthalten:

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 Verfeinerte Suche (empfohlen für Genauigkeit):

Dies ermöglicht einen genauen Jaccard-Vergleich unter Verwendung der in Milvus gespeicherten Original-Tokensätze. Sie ist etwas langsamer, wird aber für qualitätssensible Aufgaben empfohlen:

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

Index-Parameter

Dieser Abschnitt bietet einen Überblick über die Parameter, die für den Aufbau eines Index und die Durchführung von Suchvorgängen im Index verwendet werden.

Indexaufbau-Parameter

In der folgenden Tabelle sind die Parameter aufgeführt, die in params beim Aufbau eines Indexes konfiguriert werden können.

Parameter	Beschreibung	Wertebereich	Tuning-Vorschlag
mh_element_bit_width	Bitbreite der einzelnen Hash-Werte in der MinHash-Signatur. Muss durch 8 teilbar sein.	8, 16, 32, 64	Verwenden Sie 32 für eine ausgewogene Leistung und Genauigkeit. Verwenden Sie 64 für höhere Genauigkeit bei größeren Datensätzen. Verwenden Sie 16, um bei akzeptablen Genauigkeitsverlusten Speicherplatz zu sparen.
mh_lsh_band	Anzahl der Bänder zur Unterteilung der MinHash-Signatur für LSH. Steuert den Kompromiss zwischen Rückruf und Leistung.	[1, signature_length]	Für 128-dim-Signaturen: beginnen Sie mit 32 Bändern (4 Werte/Band). Erhöhen Sie den Wert auf 64 für eine höhere Wiedererkennung, verringern Sie ihn auf 16 für eine bessere Leistung. Die Signaturlänge muss gleichmäßig aufgeteilt werden.
mh_lsh_code_in_mem	Ob LSH-Hash-Codes im anonymen Speicher gespeichert werden sollen (true) oder ob eine Speicherzuordnung verwendet werden soll (false).	wahr, falsch	Verwenden Sie false für große Datensätze (>1M Sätze), um die Speichernutzung zu reduzieren. Verwenden Sie true für kleinere Datensätze, die maximale Suchgeschwindigkeit erfordern.
with_raw_data	Ob die ursprünglichen MinHash-Signaturen neben den LSH-Codes zur Verfeinerung gespeichert werden sollen.	wahr, falsch	Verwenden Sie true, wenn hohe Präzision erforderlich ist und die Speicherkosten akzeptabel sind. Verwenden Sie false, um den Speicheraufwand zu minimieren und die Genauigkeit leicht zu verringern.
mh_lsh_bloom_false_positive_prob	Falsch-Positiv-Wahrscheinlichkeit für Bloom-Filter, die in der LSH-Bucket-Optimierung verwendet werden.	[0.001, 0.1]	Verwenden Sie 0.01 für eine ausgewogene Speichernutzung und Genauigkeit. Niedrigere Werte (0.001) reduzieren Falsch-Positive, erhöhen aber den Speicherbedarf. Höhere Werte (0.05) sparen Speicherplatz, können aber die Genauigkeit verringern.

Indexspezifische Suchparameter

In der folgenden Tabelle sind die Parameter aufgeführt, die in search_params.params für die Suche im Index konfiguriert werden können.

Parameter	Beschreibung	Wertebereich	Tuning-Vorschlag
mh_search_with_jaccard	Ob eine exakte Jaccard-Ähnlichkeitsberechnung für Kandidatenergebnisse zur Verfeinerung durchgeführt werden soll.	wahr, falsch	Verwenden Sie true für Anwendungen, die eine hohe Genauigkeit erfordern (z. B. Deduplizierung). Verwenden Sie false für eine schnellere ungefähre Suche, wenn ein geringer Genauigkeitsverlust akzeptabel ist.
refine_k	Anzahl der Kandidaten, die vor der Jaccard-Verfeinerung abgerufen werden. Nur wirksam, wenn mh_search_with_jaccard true ist.	[top_k, *top_k * 10*]	Setzen Sie den Wert auf das 2-5-fache des gewünschten top_k, um ein gutes Gleichgewicht zwischen Wiederfindungsrate und Leistung zu erreichen. Höhere Werte verbessern die Wiederauffindbarkeit, erhöhen aber die Berechnungskosten.
mh_lsh_batch_search	Ob die Stapeloptimierung für mehrere gleichzeitige Abfragen aktiviert werden soll.	true, false	Verwenden Sie true, wenn Sie mit mehreren Abfragen gleichzeitig suchen, um den Durchsatz zu erhöhen. Verwenden Sie false für Szenarien mit nur einer Abfrage, um den Speicher-Overhead zu reduzieren.