Nearest neighbors graph construction: Peer sampling to the rescue

TitreNearest neighbors graph construction: Peer sampling to the rescue
Publication TypeJournal Article
Year of Publication2016
AuthorsBenkaouz, Ya, Erradi, Ma, Kermarrec, A-Mb
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9944 LNCS
Pagination48-62
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 randomness, 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. © Springer International Publishing AG 2016.

URLhttps://www.scopus.com/inward/record.uri?eid=2-s2.0-84990068831&doi=10.1007%2f978-3-319-46140-3_4&partnerID=40&md5=001c7ac565106835cc5cd7a01e01a3c4
DOI10.1007/978-3-319-46140-3_4
Revues: 

Partenaires

Localisation

Suivez-nous sur

         

    

Contactez-nous

ENSIAS

Avenue Mohammed Ben Abdallah Regragui, Madinat Al Irfane, BP 713, Agdal Rabat, Maroc

  Télécopie : (+212) 5 37 68 60 78

  Secrétariat de direction : 06 61 48 10 97

        Secrétariat général : 06 61 34 09 27

        Service des affaires financières : 06 61 44 76 79

        Service des affaires estudiantines : 06 62 77 10 17 / n.mhirich@um5s.net.ma

        Résidences : 06 61 82 89 77

Contacts

    

    Compteur de visiteurs:540,025
    Education - This is a contributing Drupal Theme
    Design by WeebPal.