Nearest Neighbors Graph Construction: Peer Sampling to the Rescue

Abstract : In this paper, we propose an efficient KNN service, called KPS (KNN-Peer-Sampling). The KPS service can be used in various contexts e.g. recommendation systems, information retrieval and data mining. KPS borrows concepts from P2P gossip-based clustering protocols to provide a localized and efficient KNN computation in large-scale systems. KPS is a sampling-based iterative approach, combining ran-domness, to provide serendipity and avoid local minimum, and clustering , to ensure fast convergence. We compare KPS against the state of the art KNN centralized computation algorithm NNDescent, on multiple datasets. The experiments confirm the efficiency of KPS over NNDescent: KPS improves significantly on the computational cost while converging quickly to a close to optimal KNN graph. For instance, the cost, expressed in number of pairwise similarity computations, is reduced by ≈ 23% and ≈ 49% to construct high quality KNN graphs for Jester and MovieLens datasets, respectively. In addition, the randomized nature of KPS ensures eventual convergence, not always achieved with NNDescent.
Type de document :
Communication dans un congrès
4th International Conference, NETYS 2016, Marrakech, Morocco, May 18-20, 2016, Revised Selected Papers, May 2016, Marrakech, Morocco. Springer, Networked systems, 9944, pp.48 - 62, 2016, Networked Systems. 〈10.1007/978-3-319-46140-3_4〉
Liste complète des métadonnées

Littérature citée [23 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01407514
Contributeur : Javier Olivares <>
Soumis le : vendredi 2 décembre 2016 - 11:51:37
Dernière modification le : mercredi 11 avril 2018 - 02:00:37
Document(s) archivé(s) le : mardi 21 mars 2017 - 04:08:33

Fichier

paper_13.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Yahya Benkaouz, Mohammed Erradi, Anne-Marie Kermarrec. Nearest Neighbors Graph Construction: Peer Sampling to the Rescue. 4th International Conference, NETYS 2016, Marrakech, Morocco, May 18-20, 2016, Revised Selected Papers, May 2016, Marrakech, Morocco. Springer, Networked systems, 9944, pp.48 - 62, 2016, Networked Systems. 〈10.1007/978-3-319-46140-3_4〉. 〈hal-01407514〉

Partager

Métriques

Consultations de la notice

354

Téléchargements de fichiers

122