FANNG: Fast Approximate Nearest Neighbour Graphs
| FANNG: Fast Approximate Nearest Neighbour Graphs | |
|---|---|
| Data | 2014 |
| Autori | Cong Fu, Chao Xiang, Changxu Wang, Deng Cai |
| URL | https://www.semanticscholar.org/paper/8843bdc4548bd2f9b483aafe90b7ee41c8b8fdc8 |
| Topic | Approximate Nearest Neighbor Search |
| Citazioni | 241 |
Un algoritmo "Approximated Nearest Neighbour Search" (ANNS) scalabile dovrebbe essere efficiente sia in termini di memoria che di velocità.
Alcuni dei primi approcci basati su grafi hanno mostrato interessanti garanzie teoriche sulla complessità del tempo di ricerca, ma soffrono tutti del problema dell'elevata complessità del tempo di indicizzazione.
Recentemente, sono stati proposti alcuni metodi basati su grafi per ridurre la complessità dell'indicizzazione approssimando i grafi tradizionali; questi metodi hanno ottenuto prestazioni rivoluzionarie su set di dati su scala milionaria. Tuttavia, non possono ancora essere ridimensionati a database da miliardi di nodi. In questo articolo, per migliorare ulteriormente l'efficienza della ricerca e la scalabilità dei metodi basati su grafi, iniziamo introducendo quattro aspetti: (1) garantire la connettività del grafico; (2) ridurre il grado medio in uscita del grafico per una rapida traversata; (3) abbreviare il percorso di ricerca; e (4) ridurre la dimensione dell'indice. Quindi, proponiamo una nuova struttura a grafo chiamata Monotonic Relative Neighborhood Graph (MRNG) che garantisce una complessità di ricerca molto bassa (prossima al tempo logaritmico). Per ridurre ulteriormente la complessità dell'indicizzazione e renderla pratica per i problemi ANNS da miliardi di nodi, proponiamo una nuova struttura a grafo denominata Navigating Spreading-out Graph (NSG) approssimando l'MRNG. L'NSG tiene conto simultaneamente dei quattro aspetti. Esperimenti approfonditi dimostrano che NSG supera significativamente tutti gli algoritmi esistenti. Inoltre, NSG mostra prestazioni superiori nello scenario e-commerce di Taobao (Alibaba Group) ed è stato integrato nel loro motore di ricerca su scala miliardaria.
Collegamenti