L’algoritmo di ricerca vettoriale di Zilliz domina tutti e quattro i percorsi di BigANN
La sfida BigANN è una competizione culminante nel dominio della ricerca vettoriale, che promuove lo sviluppo di strutture dati di indicizzazione e algoritmi di ricerca per varianti pratiche del problema Approximate Nearest Neighbor (ANN). Zilliz è orgogliosa di essere uno degli organizzatori chiave di questa importante competizione, assistendo a soluzioni ingegnose da parte di partecipanti globali. In qualità di creatori del database vettoriale Milvus, ci siamo sentiti in dovere di contribuire con le nostre intuizioni e soluzioni alla sfida presentata.
Oggi siamo entusiasti di condividere una grande notizia: la nostra soluzione Zilliz ha superato tutte le submission e soluzioni esistenti di altri vendor in tutte e quattro le track di BigANN, ottenendo un notevole miglioramento delle prestazioni fino a 2,5x. Questo post introdurrà BigANN 2023 e approfondirà la soluzione Zilliz e i suoi risultati prestazionali.
BigANN 2023
Il benchmark ANN è uno strumento standard del settore per valutare gli algoritmi di ricerca vettoriale, ma i suoi dataset di valutazione di piccole dimensioni ne limitano l’applicabilità alle sfide di produzione del mondo reale. In risposta, è nato BigANN, che funge sia da competizione sia da iniziativa di benchmarking, affrontando questa limitazione valutando e facendo progredire gli algoritmi su dataset su larga scala.
Quest’anno, BigANN 2023 introduce sfide più significative, enfatizzando dataset più grandi (fino a 10 milioni di punti vettoriali) e scenari più complessi. La competizione presenta quattro track: varianti filtrate, out-of-distribution, sparse e streaming di ANNS, offrendo un banco di prova realistico per scenari del mondo reale.
Table1: Le quattro track di BigANN 2023
Track filtrata: Questo task utilizza il dataset YFCC 100M, selezionando 10 milioni di immagini. Richiede l’estrazione di embedding CLIP per ogni immagine e la generazione di tag che coprono aspetti come descrizione dell’immagine, modello della fotocamera, anno di acquisizione e paese, tratti da un vocabolario diversificato. La sfida consiste nell’abbinare con competenza 100.000 query, ciascuna composta da un embedding dell’immagine e tag specifici, con le immagini e i tag corrispondenti nel dataset.
Track Out-Of-Distribution(OOD): Questa track presenta ai partecipanti il dataset Yandex Text-to-Image 10M, evidenziando l’integrazione di dati cross-modali. Il dataset di base include 10 milioni di embedding di immagini dal database di ricerca visiva Yandex, generati utilizzando il modello Se-ResNext-101. Al contrario, gli embedding delle query si basano su ricerche testuali, elaborate tramite un modello diverso. La sfida principale qui è colmare efficacemente il divario tra queste diverse modalità di dati.
Track Sparse: Questa track sfrutta il dataset MSMARCO passage retrieval, caratterizzato da un’ampia raccolta di oltre 8,8 milioni di passaggi testuali codificati in vettori sparsi utilizzando il modello SPLADE. Questi vettori hanno circa 30.000 dimensioni, ma mostrano una natura sparsa. Allo stesso tempo, le quasi 7.000 query vengono elaborate tramite lo stesso modello, sebbene con meno elementi non nulli a causa della loro lunghezza concisa. Il task principale in questa track è recuperare accuratamente i risultati migliori per una determinata query, con un’enfasi specifica sul massimo prodotto interno tra i vettori delle query e i vettori del database.
Track Streaming: Questa track si basa su un segmento del dataset MS Turing, composto da 30 milioni di punti dati. I partecipanti devono seguire un "runbook" fornito, che delinea in modo dettagliato una sequenza di operazioni di inserimento, eliminazione e ricerca dei dati. Queste operazioni devono essere completate entro un’ora e con meno di 8GB di DRAM. Questa track si concentra sull’ottimizzazione del processo di gestione di queste operazioni e sul mantenimento di un indice semplificato del dataset.
In questa competizione, ogni track ha criteri distinti per il ranking degli algoritmi:
Nei track Filters, OOD e Sparse, gli algoritmi vengono valutati in base al QPS, a condizione che raggiungano un minimo del 90% di recall@10.
Nel track Streaming, gli algoritmi sono classificati in base al recall@10, con il requisito aggiuntivo di completare il runbook entro un'ora.
Tutti i test prestazionali, inclusa la nostra soluzione Zilliz, sono stati condotti su un Azure D8lds_v5 (8 vCPU e 16 GiB di memoria).
Soluzione Zilliz e relativi risultati prestazionali
Tutti i seguenti risultati aderiscono al framework di valutazione e alle linee guida stabiliti dalla competizione BigANN, garantendo un confronto equo e completo.
Track Filtered
Confronto della nostra soluzione per il track Filter (zilliz) rispetto al baseline ufficiale (faiss), al vincitore (parlayivf) e alla soluzione Pinecone. Al 90% di recall, il nostro throughput è di circa 82.000 QPS, approssimativamente 25 volte il baseline a 3.200 QPS, 2,5 volte il vincitore del track a 32.000 QPS, e molto più alto della soluzione Pinecone a 68.000 QPS.
La nostra soluzione si basa su algoritmi a grafo e sulla classificazione dei tag. Durante la fase di build, analizziamo la cardinalità di ogni potenziale combinazione di tag. Costruiamo grafi per le combinazioni con un grande numero di vettori, stabilendo al contempo indici invertiti per le altre. Durante la ricerca, scegliamo il metodo di ricerca appropriato in base alle caratteristiche uniche di ciascuna combinazione di tag.
In parallelo, classifichiamo le query in base ai tag associati. Durante la ricerca, cerchiamo ogni query in base al tag corrispondente. Questo approccio offre due vantaggi: 1) massimizza l'utilizzo della cache, e 2) consente l'accelerazione tramite moltiplicazione di matrici, particolarmente vantaggiosa durante le ricerche esaustive.
Quantizziamo i dati per accelerare i calcoli e utilizziamo SIMD per ottimizzare i calcoli delle distanze, garantendo un'elevata efficienza computazionale.
Track OOD
Confronto della nostra soluzione per il track OOD rispetto al baseline ufficiale (diskann), al vincitore del track (pyanns) e alla soluzione Pinecone (pinecone-odd). Al 90% di recall, il nostro throughput è di circa 33.000 QPS, 8 volte il baseline a circa 4.000 QPS e supera il vincitore del track a circa 23.000 QPS e la soluzione Pinecone a 26.000 QPS.
Nota: Effettuiamo questo confronto utilizzando il set di query pubblico, poiché non esiste un set di query nascosto in questo track.
La nostra soluzione si basa sulla sinergia tra algoritmi a grafo e un processo di ricerca altamente ottimizzato.
Per il calcolo, utilizziamo la quantizzazione a diversi livelli di precisione sia per la ricerca sia per il refinement e sfruttiamo la potenza di SIMD per calcoli accelerati. Prima della ricerca, clusterizziamo i vettori di query. Durante la ricerca su grafo, a ciascun cluster di query vengono assegnati punti iniziali distinti, aprendo la strada a ricerche sequenziali all'interno di ciascun cluster.
Questa strategia di clustering presenta due vantaggi: 1) un'esplorazione sequenziale di cluster diversi massimizza l'utilizzo della cache, e 2) l'allocazione di punti iniziali adattivi a cluster diversi mitiga le sfide derivanti da distribuzioni vettoriali variabili.
Inoltre, implementiamo anche una struttura dati bitset multi-livello. Abbiamo bisogno di una struttura dati per contrassegnare i punti visitati nell'intricato processo di ricerca di immagini. I metodi convenzionali spesso ricorrono a un bitset o a una tabella hash, ma ciascuno presenta svantaggi. I bitset spesso comportano un uso inefficiente della memoria e cache miss, mentre le tabelle hash offrono prestazioni scarse a causa di costanti sfavorevoli. Abbiamo innovato una struttura dati bitset multi-livello che trae ispirazione dalle tabelle delle pagine multi-livello in memoria. Questo design ottimizza l'utilizzo della cache della CPU, determinando un miglioramento significativo delle prestazioni di lettura e scrittura.
Track Sparse
Confronto della nostra soluzione per la traccia Sparse (zilliz) con il baseline ufficiale (linscan), il vincitore della traccia (pyanns) e la soluzione Pinecone (pinecone_smips). Al 90% di recall, il nostro throughput è di circa 8.200 QPS, pari a 82 volte il baseline di circa 100 QPS, e ha superato sia il vincitore della traccia a 6.000 QPS sia la soluzione Pinecone a 7.400 QPS.
In questa traccia, la nostra soluzione si basa sulla sinergia tra algoritmi su grafi e ottimizzazioni guidate da vettori sparsi. Ogni vettore sparso è rappresentato come un elenco di tuple (data[float32], index[int32]). Introduciamo una quantizzazione a precisione multipla per elaborare i dati, rispondendo alle esigenze dei calcoli durante la ricerca sul grafo e il successivo raffinamento. Inoltre, ottimizziamo la larghezza di banda della memoria rappresentando l’indice con int16.
Il compito riguarda la massimizzazione della ricerca del prodotto interno. Nei calcoli del prodotto interno, le loro magnitudini influenzano l’importanza dei valori. Magnitudini maggiori hanno maggiore rilevanza, mentre quelle minori sono meno importanti. Sfruttando questa intuizione, implementiamo una strategia di pruning durante la ricerca sul grafo, scartando i valori con magnitudini assolute minori. Dopo la ricerca sul grafo, conduciamo il raffinamento utilizzando i vettori completi. I risultati sperimentali indicano che possiamo effettuare il pruning di oltre l’80% dei dati nei vettori di query senza compromettere significativamente la recall.
Utilizziamo la tecnologia SIMD per la rapida intersezione di liste ordinate per calcoli veloci, ottenendo così calcoli altamente efficienti per i prodotti interni di vettori sparsi.
Traccia Streaming
Confronto della nostra soluzione per la traccia Streaming (zilliz) con il baseline ufficiale (diskann), il vincitore della traccia (puck) e la soluzione Pinecone (pinecone). Il nostro algoritmo raggiunge una recall di 0,9982, superando il vincitore della traccia e la soluzione Pinecone con recall rispettivamente di 0,986 e 0,9975.
La nostra soluzione per la traccia streaming si basa su algoritmi su grafi e quantizzazione SQ.
Implementiamo una strategia di eliminazione lazy per le operazioni di eliminazione, marcando i vettori per l’eliminazione senza modificare immediatamente la struttura del grafo. Il grafo non viene ristrutturato finché non si accumula un numero specificato di operazioni di eliminazione.
Quantizziamo i vettori a varie precisioni sia per la ricerca sul grafo sia per il raffinamento. Innanzitutto, usiamo vettori a precisione inferiore per la ricerca sul grafo. Tuttavia, a causa della nostra strategia di eliminazione lazy, vettori eliminati possono comparire nei risultati di ricerca. Quindi, sfruttiamo una strategia di post-filtraggio per eliminare questi vettori eliminati. Infine, usiamo vettori quantizzati a precisione più elevata per affinare i risultati.
Nota: Sebbene la nostra soluzione non sia open source, abbiamo spiegato la nostra metodologia e rilasciato i binari sul repo GitHub di BigANN per un’ampia accessibilità e riproduzione.
Gli algoritmi BigANN saranno integrati nei prodotti Zilliz
Con il progresso dell’AI, la ricerca vettoriale è diventata essenziale per supportare scenari di produzione complessi. La copertura di BigANN di molteplici scenari aggiunge un significativo valore pratico. Siamo entusiasti di essere attivamente coinvolti in questa competizione BigANN e ci piace affrontare questi impegnativi problemi algoritmici. Incorporeremo gli insight derivanti da questo processo nei nostri prodotti, estendendo il loro impatto a una gamma più ampia di questioni.
Vieni a unirti a noi!
In Zilliz, ci impegniamo a costruire il miglior database vettoriale al mondo, usando la ricerca vettoriale per affrontare problemi reali. Siamo anche in un percorso continuo di esplorazione di casi d’uso impegnativi ispirati da BigANN e oltre. Invitiamo persone con interessi affini nella ricerca vettoriale, nei sistemi di database o nelle tecnologie AI a unirsi a noi in questo percorso. Se sei interessato, contattaci! Esplora le opportunità sulla nostra pagina career per maggiori informazioni e per candidarti.
Questo post è scritto da Li Liu e Zihao Wang.
Continua a leggere
How to Build an Enterprise-Ready RAG Pipeline on AWS with Bedrock, Zilliz Cloud, and LangChain
Build production-ready enterprise RAG with AWS Bedrock, Nova models, Zilliz Cloud, and LangChain. Complete tutorial with deployable code.
Expanding Our Global Reach: Zilliz Cloud Launches in Azure Central India
Zilliz Cloud expands to Azure Central India. This new region helps customers meet compliance, reduce latency, and optimize cloud costs when building AI applications.
The Great AI Agent Protocol Race: Function Calling vs. MCP vs. A2A
Compare Function Calling, MCP, and A2A protocols for AI agents. Learn which standard best fits your development needs and future-proof your applications.