IVF_PQ

Der IVF_PQ-Index ist ein quantisierungsbasierter Indizierungsalgorithmus für die ungefähre Suche nach dem nächsten Nachbarn in hochdimensionalen Räumen. IVF_PQ ist zwar nicht so schnell wie einige graphenbasierte Methoden, benötigt aber oft deutlich weniger Speicherplatz, was ihn zu einer praktischen Wahl für große Datensätze macht.

Überblick

IVF_PQ steht für Inverted File with Product Quantization (Invertierte Datei mit Produktquantisierung), ein hybrider Ansatz, der Indizierung und Komprimierung für effiziente Vektorsuche und -abfrage kombiniert. Dabei werden zwei Kernkomponenten genutzt: Invertierte Datei (IVF) und Produktquantisierung (PQ).

IVF

IVF ist wie die Erstellung eines Index in einem Buch. Anstatt jede Seite (oder in unserem Fall jeden Vektor) zu durchsuchen, suchen Sie nach bestimmten Schlüsselwörtern (Clustern) im Index, um die relevanten Seiten (Vektoren) schnell zu finden. In unserem Szenario werden die Vektoren in Clustern gruppiert, und der Algorithmus sucht in einigen wenigen Clustern, die nahe am Abfragevektor liegen.

Und so funktioniert's:

1. Clustering: Ihr Vektordatensatz wird mithilfe eines Clustering-Algorithmus wie k-means in eine bestimmte Anzahl von Clustern unterteilt. Jeder Cluster hat einen Zentroid (einen repräsentativen Vektor für den Cluster).
2. Zuweisung: Jeder Vektor wird dem Cluster zugewiesen, dessen Zentroid ihm am nächsten ist.
3. Invertierter Index: Es wird ein Index erstellt, der jeden Clusterschwerpunkt auf die Liste der diesem Cluster zugeordneten Vektoren abbildet.
4. Suche: Bei der Suche nach den nächsten Nachbarn vergleicht der Suchalgorithmus Ihren Abfragevektor mit den Clusterschwerpunkten und wählt den/die vielversprechendsten Cluster aus. Die Suche wird dann auf die Vektoren innerhalb dieser ausgewählten Cluster eingegrenzt.

Weitere Informationen zu den technischen Details finden Sie unter IVF_FLAT.

PQ

DieProduktquantisierung (PQ) ist eine Komprimierungsmethode für hochdimensionale Vektoren, die den Speicherbedarf erheblich reduziert und gleichzeitig schnelle Ähnlichkeitssuchoperationen ermöglicht.

Der PQ-Prozess umfasst die folgenden Hauptschritte:

pq-prozess-1

1. Dekomposition der Dimensionen: Der Algorithmus beginnt mit der Zerlegung jedes hochdimensionalen Vektors in m gleich große Untervektoren. Durch diese Zerlegung wird der ursprünglich D-dimensionale Raum in m disjunkte Unterräume transformiert, wobei jeder Unterraum D/m Dimensionen enthält. Der Parameter m steuert die Granularität der Zerlegung und beeinflusst direkt die Kompressionsrate.
2. Erzeugung eines Unterraum-Codebuchs: In jedem Unterraum wendet der Algorithmus das k-means-Clustering an, um einen Satz repräsentativer Vektoren (Zentroide) zu lernen. Diese Zentroide bilden zusammen ein Codebuch für diesen Unterraum. Die Anzahl der Zentroide in jedem Codebuch wird durch den Parameter nbits bestimmt, wobei jedes Codebuch 2^nbits Zentroide enthält. Wenn beispielsweise nbits = 8 verwendet wird, enthält jedes Codebuch 256 Zentroide. Jedem Zentroid wird ein eindeutiger Index mit nbits Bits zugewiesen.
3. Vektorquantisierung: Für jeden Untervektor des ursprünglichen Vektors identifiziert PQ den nächstgelegenen Schwerpunkt innerhalb des entsprechenden Unterraums unter Verwendung eines bestimmten metrischen Typs. Durch diesen Prozess wird jeder Untervektor effektiv auf den nächstgelegenen repräsentativen Vektor im Codebuch abgebildet. Anstatt die vollständigen Koordinaten des Untervektors zu speichern, wird nur der Index des übereinstimmenden Schwerpunkts beibehalten.
4. Komprimierte Darstellung: Die endgültige komprimierte Darstellung besteht aus m Indizes, einem aus jedem Unterraum, die zusammen als PQ-Codes bezeichnet werden. Diese Kodierung reduziert den Speicherbedarf von D × 32 Bits (unter der Annahme von 32-Bit-Gleitkommazahlen) auf m × n Bits, wodurch eine erhebliche Komprimierung erreicht wird, während die Fähigkeit zur Annäherung der Vektorabstände erhalten bleibt.

Weitere Einzelheiten zur Parametereinstellung und -optimierung finden Sie unter Indexparameter.

Abstandsberechnung mit PQ

Bei der Durchführung einer Ähnlichkeitssuche mit einem Abfragevektor ermöglicht PQ eine effiziente Abstandsberechnung durch die folgenden Schritte:

1. Vorverarbeitung der Abfrage

   1. Der Abfragevektor wird in m Untervektoren zerlegt, die der ursprünglichen PQ-Zerlegungsstruktur entsprechen.
   2. Für jeden Untervektor der Abfrage und sein entsprechendes Codebuch (mit 2^nbits Zentren) werden die Abstände zu allen Zentren berechnet und gespeichert.
   3. Dies erzeugt m Nachschlagetabellen, wobei jede Tabelle 2^nbits Abstände enthält.

2. Annäherung der Abstände

   Für jeden Datenbankvektor, der durch PQ-Codes dargestellt wird, wird sein ungefährer Abstand zum Abfragevektor wie folgt berechnet:

   1. Für jeden der m Untervektoren wird der vorberechnete Abstand aus der entsprechenden Nachschlagetabelle unter Verwendung des gespeicherten Schwerpunktindexes abgerufen.
   2. Summieren Sie diese m Abstände, um den ungefähren Abstand auf der Grundlage eines bestimmten metrischen Typs (z. B. Euklidischer Abstand) zu erhalten.

pq-prozess-1

IVF + PQ

Der Index IVF_PQ kombiniert die Stärken von IVF und PQ, um die Suche zu beschleunigen. Das Verfahren arbeitet in zwei Schritten:

1. Grobfilterung mit IVF: IVF partitioniert den Vektorraum in Cluster, wodurch der Suchumfang reduziert wird. Anstatt den gesamten Datensatz auszuwerten, konzentriert sich der Algorithmus nur auf die Cluster, die dem Abfragevektor am nächsten liegen.
2. Feinkörniger Vergleich mit PQ: Innerhalb der ausgewählten Cluster verwendet PQ komprimierte und quantisierte Vektordarstellungen, um ungefähre Abstände schnell zu berechnen.

Die Leistung des IVF_PQ-Index wird erheblich von den Parametern beeinflusst, die sowohl den IVF- als auch den PQ-Algorithmus steuern. Die Abstimmung dieser Parameter ist entscheidend, um optimale Ergebnisse für einen bestimmten Datensatz und eine bestimmte Anwendung zu erzielen. Ausführlichere Informationen zu diesen Parametern und deren Einstellung finden Sie unter Indexparameter.

Index erstellen

Um einen IVF_PQ -Index auf einem 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="IVF_PQ", # 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": 4, # Number of sub-vectors to split eahc vector into
    } # Index building params
)

In dieser Konfiguration:

• index_type: Der Typ des zu erstellenden Index. In diesem Beispiel setzen Sie den Wert auf IVF_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.

  • m: Anzahl der Untervektoren, in die der Vektor aufgeteilt werden soll.

  Weitere Informationen zu den für den Index IVF_PQ verfügbaren Parametern finden Sie unter Parameter für den Indexaufbau.

Sobald die Index-Parameter konfiguriert sind, können Sie den Index erstellen, indem Sie die Methode create_index() direkt verwenden oder die Index-Parameter 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": {
        "nprobe": 10, # Number of clusters to search
    }
}

res = MilvusClient.search(
    collection_name="your_collection_name", # Collection 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.

  • nprobe: Anzahl der Cluster, nach denen gesucht werden soll.

  Weitere Suchparameter, die für den Index IVF_PQ verfügbar sind, 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
IVF	nlist	Die Anzahl der Cluster, die mit dem k-means-Algorithmus während der Indexerstellung erstellt werden.	Typ: Integer Bereich: [1, 65536] Standardwert: 128	Größere nlist Werte verbessern die Wiederauffindbarkeit durch die Erstellung von feineren Clustern, erhöhen aber die Indexerstellungszeit. Optimieren Sie den Wert anhand der Größe des Datensatzes und der verfügbaren Ressourcen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs festzulegen: [32, 4096].
PQ	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 m Wert 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 innerhalb dieses Bereichs 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, das jeweils 2^nbits Zentroide enthält. Wenn zum Beispiel nbits auf 8 gesetzt ist, wird jeder Untervektor durch einen 8-Bit-Schwerpunktindex dargestellt. Dies ermöglicht 2^8 (256) mögliche Zentroide im Codebuch für diesen Untervektor.	Typ: Integer Bereich: [1, 64] 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].

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
IVF	nprobe	Die Anzahl der Cluster, in denen nach Kandidaten gesucht wird.	Typ: Ganzzahl Bereich: [1, nlist] Standardwert: 8	Höhere Werte ermöglichen die Suche nach mehr Clustern, was die Wiederauffindbarkeit durch Erweiterung des Suchbereichs verbessert, jedoch auf Kosten einer erhöhten Abfrage-Latenz. Stellen Sie nprobe proportional zu nlist ein, um Geschwindigkeit und Genauigkeit auszugleichen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs festzulegen: [1, nlist].