Zilliz-Vektorsuchalgorithmus dominiert alle vier Tracks von BigANN
Die BigANN-Challenge ist ein Höhepunkt des Wettbewerbs im Bereich der Vektorsuche und fördert die Entwicklung von Indexierungsdatenstrukturen und Suchalgorithmen für praktische Varianten des Problems der Approximate Nearest Neighbor (ANN). Zilliz ist stolz darauf, ein wichtiger Organisator dieses bedeutenden Wettbewerbs zu sein und geniale Lösungen von Teilnehmenden aus aller Welt mitzuerleben. Als Entwickler der Milvus-Vektordatenbank fühlten wir uns verpflichtet, unsere Erkenntnisse und Lösungen zu der gestellten Herausforderung beizutragen.
Heute freuen wir uns, einige großartige Neuigkeiten zu teilen: Unsere Zilliz-Lösung übertraf alle bestehenden Einreichungen und Lösungen anderer Anbieter in allen vier Tracks von BigANN und erzielte eine bemerkenswerte Leistungssteigerung von bis zu 2,5x. Dieser Beitrag stellt BigANN 2023 vor und geht ausführlich auf die Zilliz-Lösung und ihre Leistungsergebnisse ein.
BigANN 2023
Der ANN benchmark ist ein Branchenstandard-Tool zur Bewertung von Vektorsuchalgorithmen, doch seine kleinen Evaluierungsdatensätze schränken seine Anwendbarkeit auf reale Produktionsherausforderungen ein. Als Reaktion darauf entstand BigANN und dient sowohl als Wettbewerb als auch als Benchmarking-Initiative, die diese Einschränkung adressiert, indem Algorithmen auf groß angelegten Datensätzen bewertet und weiterentwickelt werden.
In diesem Jahr führt BigANN 2023 bedeutendere Herausforderungen ein, mit Schwerpunkt auf größeren Datensätzen (bis zu 10 Millionen Vektorpunkte) und komplexeren Szenarien. Der Wettbewerb umfasst vier Tracks: gefilterte, Out-of-Distribution-, Sparse- und Streaming-Varianten von ANNS und bietet damit ein realistisches Testfeld für reale Szenarien.
Table1: Die vier Tracks von BigANN 2023
Filtered Track: Diese Aufgabe verwendet den YFCC 100M-Datensatz und wählt 10 Millionen Bilder aus. Sie erfordert das Extrahieren von CLIP-Embeddings für jedes Bild und das Generieren von Tags, die Aspekte wie Bildbeschreibung, Kameramodell, Aufnahmejahr und Land abdecken und aus einem vielfältigen Vokabular stammen. Die Herausforderung besteht darin, 100.000 Abfragen kompetent abzugleichen, die jeweils aus einem Bild-Embedding und spezifischen Tags bestehen, mit den entsprechenden Bildern und Tags im Datensatz.
Out-Of-Distribution(OOD) Track: Dieser Track stellt den Teilnehmenden den Yandex Text-to-Image 10M-Datensatz zur Verfügung und hebt die Integration von cross-modalen Daten hervor. Der Basisdatensatz umfasst 10 Millionen Bild-Embeddings aus der visuellen Suchdatenbank von Yandex, die mit dem Se-ResNext-101-Modell generiert wurden. Im Gegensatz dazu basieren die Abfrage-Embeddings auf textuellen Suchen, die durch ein anderes Modell verarbeitet werden. Die zentrale Herausforderung besteht darin, die Lücke zwischen diesen unterschiedlichen Datenmodalitäten effektiv zu überbrücken.
Sparse Track: Dieser Track nutzt den MSMARCO-Passage-Retrieval-Datensatz mit einer umfangreichen Sammlung von über 8,8 Millionen Textpassagen, die mithilfe des SPLADE-Modells in Sparse-Vektoren codiert wurden. Diese Vektoren haben etwa 30.000 Dimensionen, weisen jedoch eine Sparse-Struktur auf. Gleichzeitig werden die nahezu 7.000 Abfragen durch dasselbe Modell verarbeitet, allerdings aufgrund ihrer knappen Länge mit weniger Nicht-Null-Elementen. Die Hauptaufgabe in diesem Track besteht darin, die Top-Ergebnisse für eine gegebene Abfrage präzise abzurufen, mit besonderem Schwerpunkt auf dem maximalen inneren Produkt zwischen den Abfragevektoren und den Datenbankvektoren.
Streaming Track: Dieser Track basiert auf einem Segment des MS Turing-Datensatzes mit 30 Millionen Datenpunkten. Die Teilnehmenden müssen einem bereitgestellten "runbook" folgen, das eine Abfolge von Dateneinfüge-, Lösch- und Suchoperationen detailliert beschreibt. Diese Operationen müssen innerhalb einer Stunde und mit weniger als 8GB DRAM abgeschlossen werden. Dieser Track konzentriert sich auf die Optimierung des Prozesses zur Handhabung dieser Operationen und auf die Aufrechterhaltung eines schlanken Index des Datensatzes.
In diesem Wettbewerb hat jeder Track eigene Kriterien für das Algorithmus-Ranking:
In den Tracks Filters, OOD und Sparse werden Algorithmen auf Basis von QPS bewertet, sofern sie mindestens 90 % recall@10 erreichen.
Im Streaming-Track werden Algorithmen nach recall@10 eingestuft, mit der zusätzlichen Anforderung, das Runbook innerhalb einer Stunde abzuschließen.
Alle Leistungstests, einschließlich unserer Zilliz-Lösung, wurden auf einer Azure D8lds_v5 (8 vCPUs und 16 GiB Arbeitsspeicher) durchgeführt.
Zilliz-Lösung und ihre Leistungsergebnisse
Alle folgenden Ergebnisse entsprechen dem Bewertungsrahmen und den Richtlinien des BigANN-Wettbewerbs und gewährleisten einen fairen und umfassenden Vergleich.
Filtered Track
Vergleich unserer Filter-Track-Lösung (zilliz) mit der offiziellen Baseline (faiss), dem Gewinner (parlayivf) und der Pinecone-Lösung. Bei 90 % Recall liegt unser Durchsatz bei etwa 82.000 QPS, ungefähr 25-mal so hoch wie die Baseline mit 3.200 QPS, 2,5-mal so hoch wie der Track-Gewinner mit 32.000 QPS und deutlich höher als die Pinecone-Lösung mit 68.000 QPS.
Unsere Lösung basiert auf Graphalgorithmen und Tag-Klassifizierung. Während der Build-Phase analysieren wir die Kardinalität jeder potenziellen Tag-Kombination. Wir konstruieren Graphen für Kombinationen mit einer großen Anzahl von Vektoren und erstellen gleichzeitig invertierte Indizes für andere. Bei der Suche wählen wir die geeignete Suchmethode basierend auf den einzigartigen Eigenschaften jeder Tag-Kombination.
Parallel dazu klassifizieren wir Abfragen entsprechend ihren zugehörigen Tags. Während der Suche suchen wir für jede Abfrage basierend auf ihrem entsprechenden Tag. Dieser Ansatz bietet zwei Vorteile: 1) Er maximiert die Nutzung des Caches, und 2) er ermöglicht Beschleunigung durch Matrixmultiplikation, was insbesondere bei erschöpfenden Suchen vorteilhaft ist.
Wir quantisieren Daten, um Berechnungen zu beschleunigen, und verwenden SIMD zur Feinabstimmung von Distanzberechnungen, wodurch eine hohe Recheneffizienz gewährleistet wird.
OOD Track
Vergleich unserer OOD-Track-Lösung mit der offiziellen Baseline (diskann), dem Track-Gewinner (pyanns) und der Pinecone-Lösung (pinecone-odd). Bei 90 % Recall liegt unser Durchsatz bei etwa 33.000 QPS, 8-mal so hoch wie die Baseline mit rund 4.000 QPS, und übertrifft den Track-Gewinner mit ungefähr 23.000 QPS sowie die Pinecone-Lösung mit 26.000 QPS.
Hinweis: Wir führen diesen Vergleich mit dem öffentlichen Query-Set durch, da es in diesem Track kein verborgenes Query-Set gibt.
Unsere Lösung basiert auf der Synergie von Graphalgorithmen und einem hochoptimierten Suchprozess.
Für die Berechnung verwenden wir Quantisierung auf unterschiedlichen Präzisionsstufen sowohl für die Suche als auch für die Verfeinerung und nutzen die Leistungsfähigkeit von SIMD für beschleunigte Berechnungen. Vor der Suche clustern wir Abfragevektoren. Während der Graphsuche wird jedem Cluster von Abfragen ein eigener Satz von Startpunkten zugewiesen, wodurch sequenzielle Suchen innerhalb jedes Clusters ermöglicht werden.
Diese Clustering-Strategie hat zwei Vorteile: 1) Eine sequenzielle Exploration verschiedener Cluster maximiert die Cache-Auslastung, und 2) die Zuweisung adaptiver Startpunkte zu unterschiedlichen Clustern mindert Herausforderungen, die sich aus variierenden Vektorverteilungen ergeben.
Darüber hinaus implementieren wir auch eine mehrstufige Bitset-Datenstruktur. Wir benötigen eine Datenstruktur, um besuchte Punkte im komplexen Bildsuchprozess zu markieren. Herkömmliche Methoden greifen häufig auf ein Bitset oder eine Hash-Tabelle zurück, doch beide haben Nachteile. Bitsets führen oft zu ineffizienter Speichernutzung und Cache-Misses, während Hash-Tabellen aufgrund ungünstiger Konstanten schlecht abschneiden. Wir haben eine mehrstufige Bitset-Datenstruktur entwickelt, die sich von mehrstufigen Seitentabellen im Speicher inspirieren lässt. Dieses Design optimiert die Nutzung des CPU-Caches, was zu einer erheblichen Verbesserung der Lese- und Schreibleistung führt.
Sparse Track
Vergleich unserer Sparse-Track-Lösung (zilliz) mit der offiziellen Baseline (linscan), dem Track-Gewinner (pyanns) und der Pinecone-Lösung (pinecone_smips). Bei 90 % Recall liegt unser Durchsatz bei etwa 8.200 QPS, was dem 82-Fachen der Baseline mit etwa 100 QPS entspricht, und übertraf sowohl den Track-Gewinner mit 6.000 QPS als auch die Pinecone-Lösung mit 7.400 QPS.
In diesem Track basiert unsere Lösung auf der Synergie von Graphalgorithmen und Optimierungen, die durch Sparse Vectors vorangetrieben werden. Jeder Sparse Vector wird als Liste von Tupeln (data[float32], index[int32]) dargestellt. Wir führen Multi-Precision-Quantisierung ein, um die Daten zu verarbeiten, zugeschnitten auf Berechnungen während der Graphsuche und der anschließenden Verfeinerung. Zusätzlich optimieren wir die Speicherbandbreite, indem wir den Index mit int16 darstellen.
Bei der Aufgabe geht es um die Maximierung der Inner-Product-Suche. Bei Inner-Product-Berechnungen beeinflussen ihre Beträge die Wichtigkeit der Werte. Größere Beträge haben eine höhere Bedeutung, während kleinere weniger wichtig sind. Auf Grundlage dieser Erkenntnis implementieren wir während der Graphsuche eine Pruning-Strategie, bei der Werte mit kleineren absoluten Beträgen verworfen werden. Nach der Graphsuche führen wir eine Verfeinerung mit den vollständigen Vektoren durch. Experimentelle Ergebnisse zeigen, dass wir über 80 % der Daten in Query-Vektoren entfernen können, ohne den Recall erheblich zu beeinträchtigen.
Wir setzen SIMD-Technologie für die schnelle Schnittmengenbildung sortierter Listen ein, um Berechnungen zu beschleunigen und dadurch hocheffiziente Berechnungen für Sparse-Vector-Inner-Products zu erreichen.
Streaming Track
Vergleich unserer Streaming-Track-Lösung (zilliz) mit der offiziellen Baseline (diskann), dem Track-Gewinner (puck) und der Pinecone-Lösung (pinecone). Unser Algorithmus erreicht einen Recall von 0,9982 und übertrifft damit den Track-Gewinner und die Pinecone-Lösung mit Recalls von 0,986 bzw. 0,9975.
Unsere Streaming-Track-Lösung basiert auf Graphalgorithmen und SQ-Quantisierung.
Wir implementieren eine Lazy-Deletion-Strategie für Löschoperationen, bei der Vektoren zur Löschung markiert werden, ohne die Graphstruktur sofort zu ändern. Der Graph wird erst dann umstrukturiert, wenn sich eine bestimmte Anzahl von Löschoperationen angesammelt hat.
Wir quantisieren Vektoren mit verschiedenen Präzisionen sowohl für die Graphsuche als auch für die Verfeinerung. Zunächst verwenden wir Vektoren mit niedrigerer Präzision für die Graphsuche. Aufgrund unserer Lazy-Deletion-Strategie können gelöschte Vektoren jedoch in Suchergebnissen erscheinen. Daher nutzen wir eine Post-Filtering-Strategie, um diese gelöschten Vektoren zu eliminieren. Abschließend verwenden wir höherpräzise quantisierte Vektoren, um die Ergebnisse zu verfeinern.
Hinweis: Obwohl unsere Lösung nicht open-sourced ist, haben wir unsere Methodik erläutert und die Binaries im BigANN's GitHub repo veröffentlicht, um eine breite Zugänglichkeit und Reproduzierbarkeit zu ermöglichen.
BigANN-Algorithmen werden in Zilliz-Produkte integriert
Mit dem Fortschritt der KI ist die Vektorsuche unverzichtbar geworden, um komplexe Produktionsszenarien zu unterstützen. Die Abdeckung mehrerer Szenarien durch BigANN bietet erheblichen praktischen Wert. Wir freuen uns sehr, aktiv an diesem BigANN-Wettbewerb beteiligt zu sein, und genießen es, diese anspruchsvollen algorithmischen Probleme anzugehen. Wir werden die Erkenntnisse aus diesem Prozess in unsere Produkte einfließen lassen und ihre Wirkung auf ein breiteres Spektrum von Fragestellungen ausdehnen.
Komm zu uns!
Bei Zilliz setzen wir uns dafür ein, die weltweit beste Vektordatenbank zu entwickeln und mithilfe der Vektorsuche reale Probleme zu lösen. Außerdem befinden wir uns auf einer fortlaufenden Reise, auf der wir anspruchsvolle Anwendungsfälle erkunden, die von BigANN und darüber hinaus inspiriert sind. Wir laden Gleichgesinnte, die sich für Vektorsuche, Datenbanksysteme oder KI-Technologien interessieren, ein, uns auf diesem Weg zu begleiten. Wenn du interessiert bist, melde dich! Entdecke Möglichkeiten auf unserer career-Seite, um weitere Informationen zu erhalten und dich zu bewerben.
Dieser Beitrag wurde von Li Liu und Zihao Wang verfasst.
Weiterlesen
Notion's Vector Search Is Excellent. Their Next Problem Is Harder.
Notion solved vector search scaling in two years. The next bottleneck — offline context engineering, unified data, and the real-time/offline gap — is harder.
Why Teams Are Migrating from Weaviate to Zilliz Cloud — and How to Do It Seamlessly
Explore how Milvus scales for large datasets and complex queries with advanced features, and discover how to migrate from Weaviate to Zilliz Cloud.
Why Context Engineering Is Becoming the Full Stack of AI Agents
Discover how context engineering unifies prompts, RAG, and tools to build smarter, production-ready AI agents powered by Milvus.