The Pulse
PiPNN dell’University of Maryland costruisce un indice per un miliardo di vettori in meno di 20 minuti
Ricercatori dell’University of Maryland e di Google Research hanno sviluppato PiPNN, un algoritmo che costruisce un indice per la ricerca approssimata dei vicini più prossimi su un miliardo di vettori in meno di 20 minuti. Il sistema accele
AI.info Team · Scritto con l’IA · verificato ·
Gli indici di ricerca basati su grafi sono progettati per rispondere rapidamente alle query sui vicini più prossimi, ma costruirli può richiedere ore o giorni su dataset da un miliardo di punti. PiPNN, un nuovo algoritmo frutto della collaborazione tra ricercatori dell’University of Maryland e di Google Research, affronta questo collo di bottiglia: secondo i suoi autori, può costruire un indice di alta qualità per un miliardo di elementi in meno di 20 minuti. La velocità richiede però una precisazione importante sull’hardware: i test su scala di un miliardo di punti sono stati eseguiti su una macchina cloud con 288 CPU virtuali e 2,2 terabyte di memoria.
PiPNN sostituisce le ricerche nel grafo con l’elaborazione in batch
La ricerca approssimata dei vicini più prossimi aiuta i sistemi a recuperare elementi simili a quelli di una query, tra cui documenti e possibili elementi da raccomandare rappresentati come vettori. Metodi consolidati basati su grafi, come HNSW e Vamana, creano connessioni cercando in un grafo parzialmente costruito man mano che viene aggiunto ciascun punto. Il paper su PiPNN individua in questi accessi ripetuti e irregolari alla memoria una delle principali cause dei lunghi tempi di costruzione.
PiPNN, invece, divide i dati in piccoli gruppi parzialmente sovrapposti, calcola in batch le distanze tra i punti di ciascun gruppo e seleziona le connessioni candidate per l’indice. Il suo metodo HashPrune filtra gli archi ridondanti man mano che arrivano i candidati, mantenendo il grafo sparso senza dover conservare contemporaneamente in memoria tutti i candidati. «PiPNN ci consente di costruire, per la prima volta, indici di alta qualità per la ricerca approssimata dei vicini più prossimi su dataset da un miliardo di elementi in meno di 20 minuti, usando un’unica macchina multicore», scrivono Tobias Rubel, Richard Wen, Laxman Dhulipala, Lars Gottesbüren, Rajesh Jayaram e Jakub Łącki nel loro paper. Gli autori di «PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing»
Il vantaggio in velocità dipende dal confronto
Nei benchmark del paper, PiPNN costruisce gli indici fino a 12,9 volte più velocemente di HNSW e fino a 11,6 volte più velocemente di Vamana. Sono risultati massimi, non un vantaggio uniforme su tutti i dataset: il paper riporta miglioramenti medi di 10,4 volte rispetto a HNSW e di 6,32 volte rispetto a Vamana. Secondo gli autori, nei loro test gli indici di PiPNN raggiungono una qualità paragonabile a quella dei metodi principali, mentre un ulteriore passaggio di costruzione può migliorarla, a costo di tempi di costruzione più lunghi.
Gli esperimenti su un miliardo di punti hanno utilizzato quattro dataset: BigANN, DEEP, MS-SPACEV e MS-Turing. Per queste prove, il team ha usato una macchina Google Cloud c4-highmem-288 con 288 vCPU e 2,2 terabyte di DRAM. Come la descrivono gli autori, si tratta di una sola macchina, ma non di una configurazione tipica per un server.
La memoria resta un vincolo per l’impiego
Il paper mostra anche i limiti dei metodi inclusi nel confronto: MIRAGE e FastKCNA hanno superato i 2,2 terabyte di memoria disponibili e non è stato possibile valutarli sui dataset da un miliardo di punti. Il risultato dimostra quindi una notevole velocità di costruzione rispetto ai metodi che hanno completato quelle prove, non una superiorità su scala di un miliardo di punti rispetto a ogni approccio concorrente. Anche il resoconto del lavoro pubblicato il 20 ottobre dall’University of Maryland riferisce che il team sta esplorando modi per spostare le operazioni su sistemi di archiviazione meno costosi e adattare PiPNN ai dati che arrivano continuamente.
Lo stesso resoconto dell’università riferisce che Microsoft sta lavorando per integrare il codice open source nei propri sistemi, mentre i ricercatori stanno discutendo una possibile adozione con Meta e NVIDIA. Queste iniziative metterebbero alla prova la compatibilità tra un processo di costruzione più rapido, i suoi requisiti di memoria e i sistemi in produzione, nei quali le modifiche ai dati e gli aggiornamenti degli indici possono contare quanto la velocità delle query.