Skip to Main content Skip to Navigation

The many faces of approximation in KNN graph computation

Olivier Ruas 1, 2
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 metadata

Cited literature [118 references]  Display  Hide  Download
Contributor : Abes Star :  Contact Connect in order to contact the contributor
Submitted on : Wednesday, May 15, 2019 - 9:37:09 AM
Last modification on : Friday, October 8, 2021 - 6:50:33 PM


Version validated by the jury (STAR)


  • 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