I dettagli implementativi di KNN possono cambiare drasticamente le prestazioni: l’esempio dei Cover Tree

Abstract degli autori

Gli algoritmi di ricerca dei vicini più prossimi sono ampiamente utilizzati e hanno una lunga storia, ma abbiamo riscontrato che gli articoli a loro dedicati esaminano raramente i dettagli implementativi fondamentali. Questi dettagli possono incidere in misura sostanziale sulle prestazioni e quindi cambiare le conclusioni sulla superiorità di un dato algoritmo. In questo articolo ne mettiamo in evidenza l’impatto prendendo come esempio il Cover Tree e presentando RustKNN, un’implementazione unificata in Rust di tre varianti di costruzione del Cover Tree, con tre modalità di ricerca. La nostra analisi mostra che: (1) la strategia di ricerca ottimale dipende da $k$ e dal dataset (la ricerca su un singolo albero è la più veloce per $k{=}1$ su tre dei nostri quattro dataset più grandi, mentre la ricerca su due alberi è la più veloce per $k{\ge}5$ sui tre più grandi), e scegliere la modalità sbagliata può aumentare il tempo di esecuzione fino a un fattore di $7.5\times$; (2) il parametro della base del Cover Tree, fissato a 2 in teoria e a 1,3 nella pratica, non è una scelta predefinita sicura per la ricerca su due alberi: 1,3 è ottimale solo su uno dei sette dataset e, su covtype, è $1.6\times$ più lento del valore ottimale; (3) tra cinque micro-ottimizzazioni, solo il calcolo della distanza con interruzione anticipata ha un effetto costante, che cresce con la dimensionalità (nullo per $d{=}32$, pari a $1.31\times$ per $d{=}54$ e a $1.49\times$ per $d{=}784$); e (4) i benchmark di ricerca di tutti i vicini più prossimi e quelli su dati tenuti da parte producono classifiche diverse delle implementazioni. Tutte le principali tabelle dei tempi riportano le mediane di 20 allocazioni indipendenti, con intervalli di confidenza al 95% calcolati mediante bootstrap. RustKNN è open source all’indirizzo https://github.com/CrowdStrike/RustKNN.