IVF_RABITQCompatible with Milvus 2.6.x

Der IVF_RABITQ-Index ist ein auf binärer Quantisierung basierender Indizierungsalgorithmus, der FP32-Vektoren in binäre Darstellungen quantisiert. Dieser Index bietet eine außergewöhnliche Speichereffizienz mit einem Komprimierungsverhältnis von 1 zu 32 bei gleichzeitig relativ guten Wiederfindungsraten. Er unterstützt optionale Verfeinerungen, um eine höhere Wiederauffindbarkeit auf Kosten von zusätzlichem Speicherplatz zu erreichen, was ihn zu einem vielseitigen Ersatz für IVF_SQ8 und IVF_FLAT in Szenarien mit Speicherbeschränkungen macht.

Überblick

IVF_RABITQ steht für Inverted File mit RaBitQ-Quantisierung und kombiniert zwei leistungsstarke Techniken für effiziente Vektorsuche und -speicherung.

IVF

Inverted File (IVF) organisiert den Vektorraum mit Hilfe von k-means clustering in verwaltbare Regionen. Jeder Cluster wird durch einen Zentroid repräsentiert, der als Referenzpunkt für die Vektoren innerhalb dieses Clusters dient. Dieser Clustering-Ansatz reduziert den Suchraum, indem er es dem Algorithmus ermöglicht, sich bei der Abfrageverarbeitung nur auf die relevantesten Cluster zu konzentrieren.

Mehr über die technischen Details von IVF erfahren Sie unter IVF_FLAT.

RaBitQ

RaBitQ ist eine hochmoderne binäre Quantisierungsmethode mit theoretischen Garantien, die in dem Forschungspapier "RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search" von Jianyang Gao und Cheng Long vorgestellt wurde.

RaBitQ führt mehrere innovative Konzepte ein:

Angular Information Encoding: Im Gegensatz zur traditionellen räumlichen Kodierung kodiert RaBitQ Winkelinformationen durch Vektornormalisierung. In IVF_RABITQ werden die Datenvektoren anhand ihres nächstgelegenen IVF-Schwerpunkts normalisiert, wodurch die Präzision des Quantisierungsprozesses verbessert wird.

Theoretische Grundlage: Die Kernformel der Abstandsapproximation lautet:

$$\lVert \mathbf{o_r} - \mathbf{q_r} \rVert^2 \approx \lVert \mathbf{o_r} - \mathbf{c_o} \rVert^2 + \lVert \mathbf{q_r} - \mathbf{c_o} \rVert^2 - 2 \cdot C(\mathbf{o_r}, \mathbf{c_o}) \cdot \langle \tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle + C_1(\mathbf{o_r}, \mathbf{c_o})$$

Wobei:

• $or\mathbf{o_r}$ or ist ein Datenvektor aus dem Datensatz
• $qr\mathbf{q_r}$ qr ist ein Abfragevektor
• $co\mathbf{c_o}$ co ist der nächstgelegene IVF-Schwerpunktvektor für $or\mathbf{o_r}$ o r
• $C(\mathbf{o_r}, \mathbf{c_o})$ C$(\mathbf{o}$r, co ) und $C_1(\mathbf{o_r}, \mathbf{c_o})$ C ${}_{}(o$ r, c o ) sind vorberechnete Konstanten
• $o~\tilde{\mathbf{o}}$ ~ ist der quantisierte binäre Vektor, der im Index
• $\tilde{\mathbf{o}}, \mathbf{q_r} - \mathbf{c_o} \rangle$ o ~$,$ q${}_{}-$ c${}_{}⟩$ steht für die Punkt-Produkt-Operation

Berechnungseffizienz: Die binäre Natur von $o~\tilde{\mathbf{o}}$ ~ macht Entfernungsberechnungen extrem schnell, was besonders von modernen CPU-Architekturen mit dedizierten AVX-512 VPOPCNTDQ Anweisungen auf Intel Ice Lake+ oder AMD Zen 4+ Prozessoren profitiert.

Algorithmische Weiterentwicklungen: RaBitQ lässt sich effektiv mit etablierten Verfahren wie dem FastScan -Ansatz und zufälligen Rotationen kombinieren, um die Leistung zu verbessern.

IVF + RaBitQ

Der IVF_RABITQ-Index kombiniert das effiziente Clustering von IVF mit der erweiterten binären Quantisierung von RaBitQ:

1. Coarse Filtering: IVF unterteilt den Vektorraum in Cluster, wodurch der Suchumfang durch die Konzentration auf die relevantesten Clusterregionen erheblich reduziert wird.

2. Binäre Quantisierung: Innerhalb jedes Clusters komprimiert RaBitQ die Vektoren in binäre Darstellungen, wobei wesentliche Abstandsbeziehungen durch theoretische Garantien erhalten bleiben.

3. Optionale Verfeinerung: Wenn diese Option aktiviert ist, speichert der Index zusätzliche verfeinerte Daten in Formaten mit höherer Genauigkeit (SQ6, SQ8, FP16, BF16 oder FP32), um die Wiederauffindungsrate auf Kosten eines größeren Speicherplatzes zu verbessern.

Milvus implementiert IVF_RABITQ unter Verwendung der folgenden FAISS-Fabrikstrings:

• Mit Verfeinerung: "RR({dim}),IVF{nlist},RaBitQ,Refine({refine_index})"
• Ohne Verfeinerung: "RR({dim}),IVF{nlist},RaBitQ"

Index erstellen

Um einen IVF_RABITQ -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="IVF_RABITQ", # 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={
        "nlist": 1024, # Number of clusters for the index
        "refine": True, # Enable refinement for higher recall
        "refine_type": "SQ8" # Refinement data format
    } # Index building params
)

In dieser Konfiguration:

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

• 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": {
        "nprobe": 128, # Number of clusters to search
        "rbq_query_bits": 0, # Query vector quantization bits
        "refine_k": 1 # Refinement 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 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 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. Jeder Cluster, der durch einen Zentroid dargestellt wird, speichert eine Liste von Vektoren. Durch Erhöhen dieses Parameters wird die Anzahl der Vektoren in jedem Cluster reduziert, wodurch kleinere, konzentriertere Partitionen entstehen.	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].
RaBitQ	refine	Aktiviert den Verfeinerungsprozess und speichert die verfeinerten Daten.	Typ: Boolesch Bereich: [true, false] Standardwert: false	Auf true gesetzt, wenn eine Wiederfindungsrate von 0,9+ erforderlich ist. Die Aktivierung der Verfeinerung verbessert die Genauigkeit, erhöht jedoch die Speicheranforderungen und die Zeit für den Indexaufbau.
	refine_type	Definiert die Datendarstellung, die für die Verfeinerung verwendet wird, wenn refine aktiviert ist.	Typ: String Bereich: [SQ6, SQ8, FP16, BF16, FP32] Standardwert: Keine	Die aufgelisteten Werte sind in der Reihenfolge ansteigender Wiederfindungsrate, abnehmender QPS und zunehmender Speichergröße aufgeführt. SQ8 wird als Ausgangspunkt empfohlen und bietet ein gutes Gleichgewicht zwischen Genauigkeit und Ressourcenverbrauch.

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. Höhere Werte erlauben es, mehr Cluster zu durchsuchen, was die Wiederauffindbarkeit durch Erweiterung des Suchbereichs verbessert, jedoch auf Kosten einer erhöhten Abfragelatenz.	Typ: Integer Bereich: [1, nlist] Standardwert: 8	Eine Erhöhung dieses Wertes verbessert die Auffindbarkeit, kann aber die Suche verlangsamen. Stellen Sie nprobe proportional zu nlist ein, um Geschwindigkeit und Genauigkeit auszugleichen. In den meisten Fällen wird empfohlen, einen Wert innerhalb dieses Bereichs einzustellen: [1, nlist].
RaBitQ	rbq_query_bits	Legt fest, ob eine zusätzliche skalare Quantisierung eines Abfragevektors angewendet wird. Wenn der Wert auf 0 gesetzt ist, wird die Abfrage ohne Quantisierung verwendet. Bei einem Wert innerhalb von [1, 8] wird die Abfrage mit einer n-Bit-Skalarquantisierung vorverarbeitet.	Typ: Integer Bereich: [0, 8] Standardwert: 0	Der Standardwert 0 bietet die höchste Abrufrate, aber die langsamste Leistung. Wir empfehlen, die Werte 0, 8 und 6 zu testen, da sie ähnliche Abrufraten bieten, wobei 6 die schnellste ist. Verwenden Sie kleinere Werte für höhere Auffindbarkeitsanforderungen.
	refine_k	Der Verfeinerungsprozess verwendet eine qualitativ hochwertigere Quantisierung, um die erforderliche Anzahl der nächsten Nachbarn aus einem refine_k mal größeren Pool von Kandidaten auszuwählen, die mit IVF_RABITQ ausgewählt wurden.	Typ: Float Bereich: [1, float_max) Standardwert: 1	Höhere refine_k Werte verringern die QPS, erhöhen aber die Rückrufrate. Beginnen Sie mit 1 und testen Sie die Werte 2, 3, 4 und 5, um den optimalen Kompromiss zwischen QPS und Recall für Ihren Datensatz zu finden.