FANNG: Fast Approximate Nearest Neighbour Graphs

Da Wiki AI.
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

Embeddings