HNSW_PRQ

HNSW_PRQ nutzt Hierarchical Navigable Small World (HNSW)-Graphen mit Product Residual Quantization (PRQ) und bietet eine fortschrittliche Vektorindizierungsmethode, mit der Sie den Kompromiss zwischen Indexgröße und Genauigkeit fein abstimmen können. PRQ geht über die traditionelle Produktquantisierung (PQ) hinaus, indem es einen Schritt der Restquantisierung (RQ) einführt, um zusätzliche Informationen zu erfassen, was im Vergleich zu rein PQ-basierten Methoden zu einer höheren Genauigkeit oder kompakteren Indizes führt. Die zusätzlichen Schritte können jedoch zu einem höheren Rechenaufwand bei der Indexerstellung und -suche führen.

Überblick

HNSW_PRQ kombiniert zwei Indizierungstechniken: HSNW für schnelle graphbasierte Navigation und PRQ für effiziente Vektorkompression.

HNSW

HNSW konstruiert einen mehrschichtigen Graphen, bei dem jeder Knoten einem Vektor im Datensatz entspricht. In diesem Graphen sind die Knoten auf der Grundlage ihrer Ähnlichkeit miteinander verbunden, was eine schnelle Durchquerung des Datenraums ermöglicht. Die hierarchische Struktur ermöglicht es dem Suchalgorithmus, die in Frage kommenden Nachbarn einzugrenzen, wodurch der Suchprozess in hochdimensionalen Räumen erheblich beschleunigt wird.

Weitere Informationen finden Sie unter HNSW.

PRQ

PRQ ist ein mehrstufiges Vektorkompressionsverfahren, das zwei sich ergänzende Techniken kombiniert: PQ und RQ. Durch die Aufteilung eines hochdimensionalen Vektors in kleinere Untervektoren (mittels PQ) und die anschließende Quantisierung der verbleibenden Differenz (mittels RQ) erreicht PRQ eine kompakte und dennoch genaue Darstellung der ursprünglichen Daten.

Die folgende Abbildung zeigt, wie es funktioniert.

Hnsw Prq

1. Produktquantisierung (PQ)

   In dieser Phase wird der ursprüngliche Vektor in kleinere Untervektoren unterteilt, und jeder Untervektor wird auf den nächstgelegenen Schwerpunkt in einem gelernten Codebuch abgebildet. Diese Zuordnung reduziert die Datengröße erheblich, führt aber zu Rundungsfehlern, da jeder Untervektor durch einen einzigen Schwerpunkt approximiert wird. Weitere Einzelheiten finden Sie unter IVF_PQ.

2. Restquantisierung (RQ)

   Nach der PQ-Phase quantisiert RQ den Rest - die Differenz zwischen dem ursprünglichen Vektor und seiner PQ-basierten Approximation - unter Verwendung zusätzlicher Codebücher. Da dieses Residuum in der Regel sehr viel kleiner ist, kann es präziser kodiert werden, ohne dass der Speicherplatz stark zunimmt.

   Der Parameter nrq bestimmt, wie oft dieses Residuum iterativ quantisiert wird, so dass Sie das Gleichgewicht zwischen Kompressionseffizienz und Genauigkeit fein abstimmen können.

3. Endgültige Komprimierungsdarstellung

   Sobald RQ die Quantisierung des Residuums abgeschlossen hat, werden die Ganzzahlcodes von PQ und RQ zu einem einzigen komprimierten Index kombiniert. Durch die Erfassung feiner Details, die bei PQ allein möglicherweise nicht berücksichtigt werden, verbessert RQ die Genauigkeit, ohne den Speicherplatz erheblich zu vergrößern. Diese Synergie zwischen PQ und RQ ist das, was PRQ ausmacht.

HNSW + PRQ

Durch die Kombination von HNSW und PRQ behält HNSW_PRQ die schnelle graphbasierte Suche von HNSW bei und nutzt gleichzeitig die Vorteile der mehrstufigen Komprimierung von PRQ. Der Arbeitsablauf sieht wie folgt aus:

1. Datenkomprimierung: Jeder Vektor wird zunächst über PQ in eine grobe Darstellung transformiert, und dann werden die Residuen über RQ zur weiteren Verfeinerung quantisiert. Das Ergebnis ist eine Reihe von kompakten Codes, die jeden Vektor repräsentieren.

2. Graphische Konstruktion: Die komprimierten Vektoren (einschließlich der PQ- und RQ-Codes) bilden die Grundlage für den Aufbau des HNSW-Graphen. Da die Daten in einer kompakten Form gespeichert werden, benötigt der Graph weniger Speicherplatz und die Navigation durch ihn wird beschleunigt.

3. Abruf von Kandidaten: Bei der Suche verwendet HNSW die komprimierten Darstellungen, um den Graphen zu durchlaufen und einen Pool von Kandidaten zu finden. Dadurch wird die Anzahl der zu berücksichtigenden Vektoren drastisch reduziert.

4. (Optional) Verfeinerung der Ergebnisse: Die anfänglichen Kandidatenergebnisse können zur Verbesserung der Genauigkeit auf der Grundlage der folgenden Parameter verfeinert werden:

   • refine: Legt fest, ob dieser Verfeinerungsschritt aktiviert ist. Wenn er auf true gesetzt ist, berechnet das System die Abstände unter Verwendung von höherer Genauigkeit oder unkomprimierten Darstellungen neu.

   • refine_type: Gibt den Präzisionsgrad der Daten an, die während der Verfeinerung verwendet werden (z. B. SQ6, SQ8, BF16). Eine höhere Genauigkeit wie FP32 kann genauere Ergebnisse liefern, erfordert aber mehr Speicherplatz. Diese muss die Genauigkeit des ursprünglichen komprimierten Datensatzes um sq_type übersteigen.

   • refine_k: Wirkt wie ein Vergrößerungsfaktor. Wenn z. B. Ihr Top k 100 und refine_k 2 ist, ordnet das System die 200 besten Kandidaten neu und gibt die besten 100 zurück, was die Gesamtgenauigkeit erhöht.

Eine vollständige Liste der Parameter und der gültigen Werte finden Sie unter Indexparametern.

Index erstellen

Um einen HNSW_PRQ -Index für ein Vektorfeld in Milvus zu erstellen, verwenden Sie die Methode add_index() und geben Sie die Parameter index_type, metric_type und zusätzliche Parameter für den Index an.

from pymilvus import MilvusClient

# Prepare index building params
index_params = MilvusClient.prepare_index_params()

index_params.add_index(
    field_name="your_vector_field_name", # Name of the vector field to be indexed
    index_type="HNSW_PRQ", # Type of the index to create
    index_name="vector_index", # Name of the index to create
    metric_type="L2", # Metric type used to measure similarity
    params={
        "M": 30, # Maximum number of neighbors each node can connect to in the graph
        "efConstruction": 360, # Number of candidate neighbors considered for connection during index construction
        "m": 384, 
        "nbits": 8,
        "nrq": 1,
        "refine": true, # Whether to enable the refinement step
        "refine_type": "SQ8" # Precision level of data used for refinement
    } # Index building params
)

In dieser Konfiguration:

• index_type: Der Typ des zu erstellenden Index. In diesem Beispiel setzen Sie den Wert auf HNSW_PQ.

• metric_type: Die Methode zur Berechnung des Abstands zwischen Vektoren. Unterstützte Werte sind COSINE, L2 und IP. Einzelheiten finden Sie unter Metrische Typen.

• params: Zusätzliche Konfigurationsoptionen für den Aufbau des Index. Weitere Informationen finden Sie unter Indexerstellungsparameter.

Sobald die Indexparameter konfiguriert sind, können Sie den Index erstellen, indem Sie die Methode create_index() direkt verwenden oder die Indexparameter in der Methode create_collection übergeben. Weitere Informationen finden Sie unter Sammlung erstellen.

Suche im Index

Sobald der Index erstellt und die Entitäten eingefügt sind, können Sie Ähnlichkeitssuchen im Index durchführen.

search_params = {
    "params": {
        "ef": 10, # Parameter controlling query time/accuracy trade-off
        "refine_k": 1 # The magnification factor
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection name
    anns_field="vector_field",  # Vector field name
    data=[[0.1, 0.2, 0.3, 0.4, 0.5]],  # Query vector
    limit=3,  # TopK results to return
    search_params=search_params
)

In dieser Konfiguration:

• params: Zusätzliche Konfigurationsoptionen für die Suche im Index. Details finden Sie unter Indexspezifische Suchparameter.

Index-Parameter

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

Indexaufbau-Parameter

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

	Parameter	Beschreibung	Wertebereich	Tuning-Vorschlag
HNSW	M	Maximale Anzahl der Verbindungen （oder Kanten), die jeder Knoten im Graphen haben kann, einschließlich der ausgehenden und eingehenden Kanten. Dieser Parameter wirkt sich direkt auf den Indexaufbau und die Suche aus.	Typ: Integer Bereich: [2, 2048] Standardwert: 30 (bis zu 30 ausgehende und 30 eingehende Kanten pro Knoten)	Ein größerer M führt im Allgemeinen zu einer höheren Genauigkeit, erhöht jedoch den Speicheraufwand und verlangsamt sowohl den Indexaufbau als auch die Suche. M sollte für Datensätze mit hoher Dimensionalität oder wenn eine hohe Wiederauffindbarkeit entscheidend ist, erhöht werden. Verringern Sie M, wenn die Speichernutzung und die Suchgeschwindigkeit im Vordergrund stehen. In den meisten Fällen empfehlen wir Ihnen, einen Wert innerhalb dieses Bereichs zu wählen: [5, 100].
	efConstruction	Anzahl der Nachbarschaftskandidaten, die bei der Indexerstellung für eine Verbindung in Betracht gezogen werden. Für jedes neue Element wird ein größerer Pool von Kandidaten ausgewertet, aber die maximale Anzahl der tatsächlich hergestellten Verbindungen ist immer noch durch M begrenzt.	Typ: Integer Bereich: [1, int_max] Standardwert: 360	Ein höherer efConstruction führt normalerweise zu einem genaueren Index, da mehr potenzielle Verbindungen untersucht werden. Dies führt jedoch auch zu einer längeren Indizierungszeit und einem erhöhten Speicherverbrauch während des Aufbaus. Erwägen Sie, efConstruction zu erhöhen, um die Genauigkeit zu verbessern, insbesondere in Szenarien, in denen die Indizierungszeit weniger kritisch ist. Ziehen Sie eine Verringerung von efConstruction in Betracht, um den Indexaufbau zu beschleunigen, wenn Ressourcenbeschränkungen ein Problem darstellen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs festzulegen: [50, 500].
PRQ	m	Die Anzahl der Untervektoren (für die Quantisierung), in die jeder hochdimensionale Vektor während des Quantisierungsprozesses unterteilt wird.	Typ: Integer Bereich: [1, 65536] Standardwert: Keine	Ein höherer Wert von m kann die Genauigkeit verbessern, erhöht aber auch die Rechenkomplexität und den Speicherverbrauch. m muss ein Divisor der Vektordimension(D) sein, um eine korrekte Zerlegung zu gewährleisten. Ein allgemein empfohlener Wert ist m = D/2. In den meisten Fällen wird empfohlen, einen Wert in diesem Bereich zu wählen: [D/8, D].
	nbits	Die Anzahl der Bits, die verwendet werden, um den Index des Schwerpunkts jedes Untervektors in komprimierter Form darzustellen. Sie bestimmt direkt die Größe jedes Codebuchs. Jedes Codebuch enthält 2nbits Zentroide. Wenn zum Beispiel nbits auf 8 eingestellt ist, wird jeder Untervektor durch einen 8-Bit-Schwerpunktindex dargestellt. Dies ermöglicht28 (256) mögliche Schwerpunkte im Codebuch für diesen Teilvektor.	Typ: Integer Bereich: [1, 24] Standardwert: 8	Ein höherer Wert von nbits ermöglicht größere Codebücher, was zu genaueren Darstellungen der ursprünglichen Vektoren führen kann. Allerdings bedeutet dies auch, dass mehr Bits zum Speichern jedes Index verwendet werden, was zu einer geringeren Komprimierung führt. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs zu wählen: [1, 16].
	nrq	Legt fest, wie viele Restunterquantisierer in der RQ-Stufe verwendet werden. Mit mehr Unterquantisierern wird möglicherweise eine stärkere Komprimierung erreicht, aber es kann zu einem größeren Informationsverlust kommen.	Typ: Integer Bereich: [1, 16] Standardwert: 2	Ein höherer Wert von nrq erlaubt zusätzliche Subquantisierungsschritte, was zu einer genaueren Rekonstruktion der ursprünglichen Vektoren führen kann. Allerdings bedeutet dies auch, dass mehr Subquantisierer gespeichert und berechnet werden müssen, was zu einer größeren Indexgröße und einem höheren Rechenaufwand führt.
	refine	Ein boolesches Flag, das steuert, ob während der Suche ein Verfeinerungsschritt angewendet wird. Bei der Verfeinerung werden die ursprünglichen Ergebnisse neu geordnet, indem die genauen Abstände zwischen dem Abfragevektor und den Kandidaten berechnet werden.	Typ: Boolean Bereich: [true, false] Standardwert: false	Setzen Sie true, wenn hohe Genauigkeit wichtig ist und Sie etwas langsamere Suchzeiten tolerieren können. Verwenden Sie false, wenn Geschwindigkeit eine Priorität ist und ein kleiner Kompromiss bei der Genauigkeit akzeptabel ist.
	refine_type	Bestimmt die Genauigkeit der Daten, die während des Verfeinerungsprozesses verwendet werden. Diese Genauigkeit muss höher sein als die der komprimierten Vektoren (wie durch die Parameter m und nbits festgelegt).	Typ: String Bereich:[ SQ6, SQ8, BF16, FP16, FP32 ] Standardwert: Keine	Verwenden Sie FP32 für maximale Präzision bei höheren Speicherkosten oder SQ6/SQ8 für eine bessere Komprimierung. BF16 und FP16 bieten eine ausgewogene Alternative.

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
HNSW	ef	Steuert die Breite der Suche während der Suche nach den nächsten Nachbarn. Er bestimmt, wie viele Knoten besucht und als potenzielle nächste Nachbarn bewertet werden. Dieser Parameter wirkt sich nur auf den Suchprozess aus und gilt ausschließlich für die unterste Schicht des Graphen.	Typ: Integer Bereich: [1, int_max] Standardwert: limit (TopK nächste Nachbarn, die zurückgegeben werden)	Eine größere ef führt im Allgemeinen zu einer höheren Suchgenauigkeit, da mehr potenzielle Nachbarn berücksichtigt werden. Allerdings erhöht sich dadurch auch die Suchzeit. ef sollte erhöht werden, wenn eine hohe Wiederfindungsrate entscheidend ist und die Suchgeschwindigkeit weniger wichtig ist. Ziehen Sie in Erwägung, ef zu verringern, um schnelleren Suchen den Vorzug zu geben, insbesondere in Szenarien, in denen eine leichte Verringerung der Genauigkeit akzeptabel ist. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs zu wählen: [K, 10K].
PRQ	refine_k	Der Vergrößerungsfaktor, der steuert, wie viele zusätzliche Kandidaten während der Verfeinerungsphase (Reranking) im Verhältnis zu den angeforderten Top-K-Ergebnissen untersucht werden.	Typ: Float Bereich: [1, float_max) Standardwert: 1	Höhere Werte von refine_k können die Auffindbarkeit und Genauigkeit verbessern, erhöhen aber auch die Suchzeit und den Ressourcenverbrauch. Ein Wert von 1 bedeutet, dass der Verfeinerungsprozess nur die anfänglichen Top-K-Ergebnisse berücksichtigt.