Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download

https://hal.inria.fr/hal-01407514
Contributor : Javier Olivares <>
Submitted on : Friday, December 2, 2016 - 11:51:37 AM
Last modification on : Thursday, January 7, 2021 - 4:34:35 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 4:08:33 AM

File

paper_13.pdf
Files produced by the author(s)

Identifiers

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. pp.48 - 62, ⟨10.1007/978-3-319-46140-3_4⟩. ⟨hal-01407514⟩

Share

Metrics

Record views

1074

Files downloads

1270