In-Memory-Index

Indizes für Fließkomma-Einbettungen

Für 128-dimensionale Fließkomma-Einbettungen (Vektoren) beträgt der benötigte Speicherplatz 128 * die Größe von float = 512 Byte. Die für Fließkomma-Einbettungen verwendeten Abstandsmetriken sind der euklidische Abstand (L2) und das innere Produkt (IP).

Diese Arten von Indizes umfassen FLAT, IVF_FLAT, IVF_PQ, IVF_SQ8, HNSW und SCANN für CPU-basierte ANN-Suchen.

FLAT

Für Anwendungen der Vektorähnlichkeitssuche, die eine perfekte Genauigkeit erfordern und von relativ kleinen Datensätzen (im Millionenbereich) abhängen, ist der FLAT-Index eine gute Wahl. FLAT komprimiert die Vektoren nicht und ist der einzige Index, der exakte Suchergebnisse garantieren kann. Die Ergebnisse von FLAT können auch als Vergleichspunkt für Ergebnisse anderer Indizes verwendet werden, die weniger als 100 % Recall haben.

FLAT ist genau, weil er einen erschöpfenden Suchansatz verfolgt, d. h. für jede Abfrage wird die Zieleingabe mit jedem Satz von Vektoren in einem Datensatz verglichen. Dadurch ist FLAT der langsamste Index auf unserer Liste und eignet sich schlecht für die Abfrage umfangreicher Vektordaten. Für den FLAT-Index in Milvus sind keine Parameter erforderlich, und seine Verwendung erfordert kein Datentraining.

• Suchparameter

  Parameter	Beschreibung	Bereich
  metric_type	[Optional] Die gewählte Distanzmetrik.	Siehe Unterstützte Metriken.

IVF_FLAT

IVF_FLAT unterteilt Vektordaten in nlist Cluster-Einheiten und vergleicht dann die Abstände zwischen dem Ziel-Eingangsvektor und dem Zentrum jedes Clusters. Je nach Anzahl der Cluster, die das System abfragen soll (nprobe), werden die Ergebnisse der Ähnlichkeitssuche nur auf der Grundlage von Vergleichen zwischen der Zieleingabe und den Vektoren in den ähnlichsten Clustern zurückgegeben, was die Abfragezeit drastisch reduziert.

Durch die Anpassung von nprobe kann ein ideales Gleichgewicht zwischen Genauigkeit und Geschwindigkeit für ein bestimmtes Szenario gefunden werden. Die Ergebnisse des IVF_FLAT-Leistungstests zeigen, dass die Abfragezeit stark ansteigt, wenn sowohl die Anzahl der Zieleingangsvektoren (nq) als auch die Anzahl der zu durchsuchenden Cluster (nprobe) zunimmt.

IVF_FLAT ist der einfachste IVF-Index, und die in jeder Einheit gespeicherten kodierten Daten stimmen mit den Originaldaten überein.

• Parameter für den Indexaufbau

  Parameter	Beschreibung	Bereich	Standardwert
  nlist	Anzahl der Cluster-Einheiten	[1, 65536]	128

• Suchparameter

  • Gemeinsame Suche

    Parameter	Beschreibung	Bereich	Standardwert
    nprobe	Anzahl der abzufragenden Einheiten	[1, nlist]	8

  • Bereichssuche

    Parameter	Beschreibung	Bereich	Standardwert
    max_empty_result_buckets	Maximale Anzahl von Bereichen, die keine Suchergebnisse liefern. Dies ist ein Parameter für die Bereichssuche und beendet den Suchvorgang, wenn die Anzahl der aufeinanderfolgenden leeren Bereiche den angegebenen Wert erreicht. Eine Erhöhung dieses Wertes kann die Abrufrate auf Kosten einer längeren Suchzeit verbessern.	[1, 65535]	2

IVF_SQ8

IVF_FLAT führt keine Komprimierung durch, so dass die erzeugten Indexdateien ungefähr die gleiche Größe haben wie die ursprünglichen, nicht indizierten Vektordaten. Wenn z. B. der ursprüngliche 1B-SIFT-Datensatz 476 GB groß ist, sind die IVF_FLAT-Indexdateien etwas kleiner (~470 GB). Wenn alle Indexdateien in den Speicher geladen werden, werden 470 GB Speicherplatz verbraucht.

Wenn Festplatten-, CPU- oder GPU-Speicherressourcen begrenzt sind, ist IVF_SQ8 eine bessere Option als IVF_FLAT. Dieser Indextyp kann jedes FLOAT (4 Byte) in UINT8 (1 Byte) umwandeln, indem er eine Skalarquantisierung (SQ) durchführt. Dies reduziert den Festplatten-, CPU- und GPU-Speicherverbrauch um 70-75 %. Für den 1B-SIFT-Datensatz benötigen die IVF_SQ8-Indexdateien nur 140 GB Speicherplatz.

• Parameter für die Indexerstellung

  Parameter	Beschreibung	Bereich
  nlist	Anzahl der Cluster-Einheiten	[1, 65536]

• Suchparameter

  • Gemeinsame Suche

    Parameter	Beschreibung	Bereich	Standardwert
    nprobe	Anzahl der abzufragenden Einheiten	[1, nlist]	8

  • Bereichssuche

    Parameter	Beschreibung	Bereich	Standardwert
    max_empty_result_buckets	Maximale Anzahl der Buckets, die keine Suchergebnisse liefern. Dies ist ein Parameter für die Bereichssuche, der den Suchvorgang beendet, wenn die Anzahl der aufeinander folgenden leeren Buckets den angegebenen Wert erreicht. Eine Erhöhung dieses Wertes kann die Abrufrate auf Kosten einer längeren Suchzeit verbessern.	[1, 65535]	2

IVF_PQ

PQ (Produktquantisierung) zerlegt den ursprünglichen hochdimensionalen Vektorraum gleichmäßig in kartesische Produkte von m niedrigdimensionalen Vektorräumen und quantisiert dann die zerlegten niedrigdimensionalen Vektorräume. Anstatt die Abstände zwischen dem Zielvektor und dem Zentrum aller Einheiten zu berechnen, ermöglicht die Produktquantisierung die Berechnung der Abstände zwischen dem Zielvektor und dem Clustering-Zentrum jedes niedrigdimensionalen Raums und reduziert die Zeit- und Raumkomplexität des Algorithmus erheblich.

IVF_PQ führt das IVF-Index-Clustering durch, bevor das Produkt der Vektoren quantisiert wird. Seine Indexdatei ist sogar noch kleiner als IVF_SQ8, aber auch hier kommt es zu einem Verlust an Genauigkeit bei der Suche nach Vektoren.

• Parameter für den Indexaufbau

  Parameter	Beschreibung	Bereich
  nlist	Anzahl der Cluster-Einheiten	[1, 65536]
  m	Anzahl der Faktoren der Produktquantisierung	dim mod m == 0
  nbits	[Optional] Anzahl der Bits, in denen jeder niedrigdimensionale Vektor gespeichert wird.	[1, 64] (8 als Standard)

• Suchparameter

  • Allgemeine Suche

    Parameter	Beschreibung	Bereich	Standardwert
    nprobe	Anzahl der abzufragenden Einheiten	[1, nlist]	8

  • Bereichssuche

    Parameter	Beschreibung	Bereich	Standardwert
    max_empty_result_buckets	Maximale Anzahl von Bereichen, die keine Suchergebnisse liefern. Dies ist ein Parameter für die Bereichssuche und beendet den Suchvorgang, wenn die Anzahl der aufeinanderfolgenden leeren Bereiche den angegebenen Wert erreicht. Eine Erhöhung dieses Wertes kann die Abrufrate auf Kosten einer längeren Suchzeit verbessern.	[1, 65535]	2

SCANN

ScaNN (Scalable Nearest Neighbors) ähnelt IVF_PQ in Bezug auf Vektor-Clustering und Produktquantisierung. Der Unterschied liegt in den Implementierungsdetails der Produktquantisierung und der Verwendung von SIMD (Single-Instruction / Multi-data) für eine effiziente Berechnung.

• Parameter für die Indexbildung

  Parameter	Beschreibung	Bereich
  nlist	Anzahl der Cluster-Einheiten	[1, 65536]
  with_raw_data	Angabe, ob die Rohdaten in den Index aufgenommen werden sollen	True oder False. Der Standardwert ist True.

  Im Gegensatz zu IVF_PQ gelten die Standardwerte für m und nbits, um die Leistung zu optimieren.

• Suchparameter

  • Allgemeine Suche

    Parameter	Beschreibung	Bereich	Standardwert
    nprobe	Anzahl der abzufragenden Einheiten	[1, nlist]
    reorder_k	Anzahl der abzufragenden Einheiten	[top_k, ∞]	top_k

  • Bereichssuche

    Parameter	Beschreibung	Bereich	Standardwert
    max_empty_result_buckets	Maximale Anzahl der Buckets, die keine Suchergebnisse liefern. Dies ist ein Parameter für die Bereichssuche, der den Suchvorgang beendet, wenn die Anzahl der aufeinander folgenden leeren Buckets den angegebenen Wert erreicht. Eine Erhöhung dieses Wertes kann die Abrufrate auf Kosten einer längeren Suchzeit verbessern.	[1, 65535]	2

HNSW

HNSW (Hierarchical Navigable Small World Graph) ist ein graphbasierter Indizierungsalgorithmus. Er baut eine mehrschichtige Navigationsstruktur für ein Bild nach bestimmten Regeln auf. In dieser Struktur sind die oberen Schichten spärlicher und die Abstände zwischen den Knoten größer; die unteren Schichten sind dichter und die Abstände zwischen den Knoten sind kleiner. Die Suche beginnt in der obersten Schicht, findet den Knoten, der dem Ziel in dieser Schicht am nächsten liegt, und begibt sich dann in die nächste Schicht, um eine weitere Suche zu beginnen. Nach mehreren Iterationen kann sie sich schnell der Zielposition nähern.

Um die Leistung zu verbessern, begrenzt HNSW den maximalen Grad der Knoten auf jeder Ebene des Graphen auf M. Darüber hinaus können Sie efConstruction (beim Indexaufbau) oder ef (bei der Suche nach Zielen) verwenden, um einen Suchbereich anzugeben.

• Parameter für den Indexaufbau

  Parameter	Beschreibung	Bereich
  M	M definiert die maximale Anzahl der ausgehenden Verbindungen im Diagramm. Ein höheres M führt zu höherer Genauigkeit/Laufzeit bei fester ef/efConstruction.	[2, 2048]
  efConstruction	ef_construction steuert den Kompromiss zwischen Indexsuchgeschwindigkeit und Erstellungsgeschwindigkeit. Eine Erhöhung des efConstruction-Parameters kann die Indexqualität verbessern, führt aber auch zu einer Verlängerung der Indexierungszeit.	[1, int_max]

• Suchparameter

  Parameter	Beschreibung	Bereich
  ef	Parameter, der den Kompromiss zwischen Abfragezeit und -genauigkeit steuert. Eine höhere ef führt zu einer genaueren, aber langsameren Suche.	[top_k, int_max]