L’algorithme de recherche vectorielle de Zilliz domine les quatre pistes de BigANN
Le défi BigANN est une compétition majeure dans le domaine de la recherche vectorielle, favorisant le développement de structures de données d’indexation et d’algorithmes de recherche pour des variantes pratiques du problème du plus proche voisin approximatif (ANN). Zilliz est fier d’être l’un des principaux organisateurs de cette compétition importante, témoin de solutions ingénieuses proposées par des participants du monde entier. En tant que créateurs de la base de données vectorielle Milvus, nous nous sommes sentis tenus de contribuer avec nos perspectives et nos solutions au défi présenté.
Aujourd’hui, nous sommes ravis de partager une excellente nouvelle : notre solution Zilliz a surpassé toutes les soumissions existantes et les solutions d’autres fournisseurs sur les quatre pistes de BigANN, atteignant une amélioration remarquable des performances allant jusqu’à 2,5x. Cet article présentera BigANN 2023 et examinera en profondeur la solution Zilliz ainsi que ses résultats de performance.
BigANN 2023
Le benchmark ANN est un outil standard de l’industrie pour évaluer les algorithmes de recherche vectorielle, mais ses jeux de données d’évaluation de petite taille limitent son applicabilité aux défis de production réels. En réponse, BigANN a vu le jour et sert à la fois de compétition et d’initiative de benchmarking, répondant à cette limitation en évaluant et en faisant progresser les algorithmes sur des jeux de données à grande échelle.
Cette année, BigANN 2023 introduit des défis plus importants, en mettant l’accent sur des jeux de données plus volumineux (jusqu’à 10 millions de points vectoriels) et des scénarios plus complexes. La compétition comprend quatre pistes : variantes filtrée, hors distribution, clairsemée et en streaming d’ANNS, offrant un terrain d’essai réaliste pour les scénarios du monde réel.
Table1: The four tracks of BigANN 2023
Piste filtrée : Cette tâche utilise le jeu de données YFCC 100M, en sélectionnant 10 millions d’images. Elle nécessite l’extraction d’embeddings CLIP pour chaque image et la génération de tags couvrant des aspects tels que la description de l’image, le modèle de l’appareil photo, l’année de capture et le pays, issus d’un vocabulaire diversifié. Le défi consiste ici à faire correspondre efficacement 100 000 requêtes, chacune comprenant un embedding d’image et des tags spécifiques, avec leurs images et tags correspondants dans le jeu de données.
Piste hors distribution (OOD) : Cette piste propose aux participants le jeu de données Yandex Text-to-Image 10M, mettant en évidence l’intégration de données multimodales. Le jeu de données de base comprend 10 millions d’embeddings d’images provenant de la base de données de recherche visuelle de Yandex, générés à l’aide du modèle Se-ResNext-101. En revanche, les embeddings de requête sont basés sur des recherches textuelles, traitées au moyen d’un modèle différent. Le principal défi consiste ici à combler efficacement l’écart entre ces différentes modalités de données.
Piste clairsemée : Cette piste exploite le jeu de données de récupération de passages MSMARCO, comprenant une vaste collection de plus de 8,8 millions de passages textuels encodés en vecteurs clairsemés à l’aide du modèle SPLADE. Ces vecteurs comportent environ 30 000 dimensions, mais présentent une nature clairsemée. Parallèlement, les près de 7 000 requêtes sont traitées avec le même modèle, bien qu’elles comportent moins d’éléments non nuls en raison de leur longueur concise. La tâche principale de cette piste consiste à récupérer avec précision les meilleurs résultats pour une requête donnée, avec un accent particulier sur le produit scalaire interne maximal entre les vecteurs de requête et les vecteurs de la base de données.
Piste en streaming : Cette piste est basée sur un segment du jeu de données MS Turing, comprenant 30 millions de points de données. Les participants doivent suivre un "runbook" fourni, qui décrit en détail une séquence d’opérations d’insertion, de suppression et de recherche de données. Ces opérations doivent être effectuées en moins d’une heure et avec moins de 8GB de DRAM. Cette piste se concentre sur l’optimisation du processus de traitement de ces opérations et sur le maintien d’un index rationalisé du jeu de données.
Dans cette compétition, chaque piste possède des critères distincts pour le classement des algorithmes :
Dans les pistes Filters, OOD et Sparse, les algorithmes sont évalués en fonction du QPS, à condition qu’ils atteignent un minimum de 90 % de recall@10.
Dans la piste Streaming, les algorithmes sont classés selon le recall@10, avec l’exigence supplémentaire de terminer le runbook en moins d’une heure.
Tous les tests de performance, y compris notre solution Zilliz, ont été réalisés sur une Azure D8lds_v5 (8 vCPU et 16 Gio de mémoire).
Solution Zilliz et ses résultats de performance
Tous les résultats suivants respectent le cadre d’évaluation et les directives établis par la compétition BigANN, garantissant une comparaison équitable et complète.
Piste Filtered
Comparaison de notre solution de la piste Filter (zilliz) avec la référence officielle (faiss), le gagnant (parlayivf) et la solution Pinecone. À 90 % de recall, notre débit est d’environ 82 000 QPS, soit approximativement 25 fois la référence à 3 200 QPS, 2,5 fois le gagnant de la piste à 32 000 QPS, et bien supérieur à la solution Pinecone à 68 000 QPS.
Notre solution repose sur des algorithmes de graphe et la classification des tags. Pendant la phase de construction, nous analysons la cardinalité de chaque combinaison potentielle de tags. Nous construisons des graphes pour les combinaisons comportant un grand nombre de vecteurs, tout en établissant des index inversés pour les autres. Lors de la recherche, nous choisissons la méthode de recherche appropriée en fonction des caractéristiques uniques de chaque combinaison de tags.
En parallèle, nous classons les requêtes selon leurs tags associés. Pendant la recherche, nous recherchons chaque requête en fonction de son tag correspondant. Cette approche offre deux avantages : 1) elle maximise l’utilisation du cache, et 2) elle permet une accélération par multiplication matricielle, ce qui est particulièrement bénéfique lors des recherches exhaustives.
Nous quantifions les données pour accélérer les calculs et utilisons SIMD pour affiner les calculs de distance, garantissant ainsi une grande efficacité de calcul.
Piste OOD
Comparaison de notre solution de la piste OOD avec la référence officielle (diskann), le gagnant de la piste (pyanns) et la solution Pinecone (pinecone-odd). À 90 % de recall, notre débit est d’environ 33 000 QPS, soit 8 fois la référence à environ 4 000 QPS, et surpasse le gagnant de la piste à environ 23 000 QPS ainsi que la solution Pinecone à 26 000 QPS.
Remarque : Nous effectuons cette comparaison à l’aide du jeu de requêtes public, puisqu’il n’existe pas de jeu de requêtes caché sur cette piste.
Notre solution repose sur la synergie entre les algorithmes de graphe et un processus de recherche hautement optimisé.
Pour le calcul, nous utilisons la quantification à différents niveaux de précision, à la fois pour la recherche et l’affinage, et exploitons la puissance de SIMD pour accélérer les calculs. Avant la recherche, nous regroupons les vecteurs de requête en clusters. Pendant la recherche dans le graphe, chaque cluster de requêtes se voit attribuer des points initiaux distincts, ouvrant la voie à des recherches séquentielles au sein de chaque cluster.
Cette stratégie de clustering présente deux avantages : 1) une exploration séquentielle de différents clusters maximise l’utilisation du cache, et 2) l’allocation de points initiaux adaptatifs à des clusters divers atténue les difficultés liées aux distributions variables des vecteurs.
En outre, nous implémentons également une structure de données bitset multiniveau. Nous avons besoin d’une structure de données pour marquer les points visités dans le processus complexe de recherche d’images. Les méthodes conventionnelles recourent souvent à un bitset ou à une table de hachage, mais chacune présente des inconvénients. Les bitsets entraînent souvent une utilisation inefficace de la mémoire et des défauts de cache, tandis que les tables de hachage offrent de mauvaises performances en raison de constantes défavorables. Nous avons innové avec une structure de données bitset multiniveau qui s’inspire des tables de pages multiniveaux en mémoire. Cette conception optimise l’utilisation du cache CPU, entraînant une amélioration significative des performances de lecture et d’écriture.
Piste Sparse
Comparaison de notre solution pour la piste Sparse (zilliz) avec la référence officielle (linscan), le vainqueur de la piste (pyanns) et la solution Pinecone (pinecone_smips). À 90 % de rappel, notre débit est d’environ 8 200 QPS, soit 82 fois la référence à environ 100 QPS, et dépasse à la fois le vainqueur de la piste à 6 000 QPS et la solution Pinecone à 7 400 QPS.
Dans cette piste, notre solution repose sur la synergie entre les algorithmes de graphes et les optimisations pilotées par les vecteurs creux. Chaque vecteur creux est représenté sous forme d’une liste de tuples (data[float32], index[int32]). Nous introduisons une quantification à précision multiple pour traiter les données, en répondant aux besoins des calculs pendant la recherche dans le graphe et de l’affinage ultérieur. De plus, nous optimisons la bande passante mémoire en représentant l’index avec int16.
La tâche consiste à maximiser la recherche par produit scalaire. Dans les calculs de produit scalaire, leurs amplitudes influencent l’importance des valeurs. Les amplitudes plus grandes ont une importance plus élevée, tandis que les plus petites sont moins importantes. En nous appuyant sur cette observation, nous mettons en œuvre une stratégie d’élagage pendant la recherche dans le graphe, en écartant les valeurs dont l’amplitude absolue est plus faible. Après la recherche dans le graphe, nous effectuons un affinage avec les vecteurs complets. Les résultats expérimentaux indiquent que nous pouvons élaguer plus de 80 % des données des vecteurs de requête sans compromettre significativement le rappel.
Nous employons la technologie SIMD pour l’intersection rapide de listes triées afin d’accélérer les calculs, ce qui permet d’obtenir des calculs très efficaces pour les produits scalaires de vecteurs creux.
Piste Streaming
Comparaison de notre solution pour la piste Streaming (zilliz) avec la référence officielle (diskann), le vainqueur de la piste (puck) et la solution Pinecone (pinecone). Notre algorithme atteint un rappel de 0,9982, dépassant le vainqueur de la piste et la solution Pinecone, avec des rappels de 0,986 et 0,9975, respectivement.
Notre solution pour la piste Streaming repose sur des algorithmes de graphes et la quantification SQ.
Nous mettons en œuvre une stratégie de suppression paresseuse pour les opérations de suppression, en marquant les vecteurs à supprimer sans modifier immédiatement la structure du graphe. Le graphe n’est restructuré qu’après l’accumulation d’un nombre spécifié d’opérations de suppression.
Nous quantifions les vecteurs à différentes précisions pour la recherche dans le graphe comme pour l’affinage. Tout d’abord, nous utilisons des vecteurs de précision inférieure pour la recherche dans le graphe. Cependant, en raison de notre stratégie de suppression paresseuse, des vecteurs supprimés peuvent apparaître dans les résultats de recherche. Nous tirons donc parti d’une stratégie de post-filtrage pour éliminer ces vecteurs supprimés. Enfin, nous utilisons des vecteurs quantifiés de plus haute précision pour affiner les résultats.
Remarque : Bien que notre solution ne soit pas open source, nous avons expliqué notre méthodologie et publié les binaires sur le repo GitHub de BigANN afin d’en assurer une large accessibilité et reproductibilité.
Les algorithmes BigANN seront intégrés aux produits Zilliz
À mesure que l’IA progresse, la recherche vectorielle est devenue essentielle pour prendre en charge des scénarios de production complexes. La couverture de multiples scénarios par BigANN apporte une valeur pratique significative. Nous sommes ravis de participer activement à cette compétition BigANN et nous aimons relever ces défis algorithmiques exigeants. Nous intégrerons les enseignements tirés de ce processus dans nos produits, afin d’étendre leur impact à un éventail plus large de problématiques.
Venez nous rejoindre !
Chez Zilliz, nous nous engageons à construire la meilleure base de données vectorielle au monde, en utilisant la recherche vectorielle pour résoudre des problèmes concrets. Nous poursuivons également un parcours continu d’exploration de cas d’utilisation complexes inspirés par BigANN et au-delà. Nous invitons les personnes partageant les mêmes idées et intéressées par la recherche vectorielle, les systèmes de bases de données ou les technologies d’IA à nous rejoindre dans cette aventure. Si vous êtes intéressé, contactez-nous ! Consultez les opportunités sur notre page carrières pour plus d’informations et pour postuler.
Cet article est rédigé par Li Liu et Zihao Wang.
Continuer à lire
Zilliz Cloud Now Available in AWS Asia Pacific (Seoul)
Zilliz Cloud is now available in AWS Seoul — low-latency vector search, in-country data residency, and one-step migration for Korean AI teams. 31 regions across 5 clouds.
Creating Collections in Zilliz Cloud Just Got Way Easier
We've enhanced the entire collection creation experience to bring advanced capabilities directly into the interface, making it faster and easier to build production-ready schemas without switching tools.
Demystifying the Milvus Sizing Tool
Explore how to use the Sizing Tool to select the optimal configuration for your Milvus deployment.