The many faces of approximation in KNN graph computation

Olivier Ruas 1
1 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The incredible quantity of available content in online services makes content of interest incredibly difficult to find. The most emblematic way to help the users is to do item recommendation. The K-Nearest-Neighbors (KNN) graph connects each user to its k most similar other users, according to a given similarity metric. The computation time of an exact KNN graph is prohibitive in online services. Existing approaches approximate the set of candidates for each user’s neighborhood to decrease the computation time. In this thesis we push farther the notion of approximation : we approximate the data of each user, the similarity and the data locality. The resulting approach clearly outperforms all the other ones.
Document type :
Complete list of metadatas

Cited literature [98 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Wednesday, May 15, 2019 - 9:37:09 AM
Last modification on : Friday, September 13, 2019 - 9:51:33 AM


Files produced by the author(s)


  • HAL Id : tel-01938076, version 2


Olivier Ruas. The many faces of approximation in KNN graph computation. Information Retrieval [cs.IR]. Université Rennes 1, 2018. English. ⟨NNT : 2018REN1S088⟩. ⟨tel-01938076v2⟩



Record views


Files downloads