Modifica Modulo pubblicazione: FANNG: Fast Approximate Nearest Neighbour Graphs

Testo libero:

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]] [[Category:pubblicazione]] {{#seo: |title=FANNG: Fast Approximate Nearest Neighbour Graphs |title_mode=append |keywords=ricerca del vicino più prossimo, ANN, grafi, indicizzazione, scalabilità, database, data mining, MRNG, NSG |description=La ricerca approssimativa del vicino più prossimo (ANNS) è un problema cruciale. Questo studio introduce una nuova struttura a grafo, Navigating Spreading-out Graph (NSG), per migliorare l'efficienza e la scalabilità di ANNS. NSG supera gli algoritmi esistenti e mostra prestazioni superiori su set di dati su larga scala, come dimostrato nell'implementazione nel motore di ricerca di Taobao (Alibaba Group). }}