The many faces of approximation in KNN graph computation - Archive ouverte HAL Access content directly
Theses Year : 2018

The many faces of approximation in KNN graph computation

Les multiples facettes des approximations dans la construction de graphes KN

(1, 2)
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.
La quantité incroyable de contenu disponible dans les services en ligne rend le contenu intéressant incroyablement difficile à trouver. La manière la plus emblématique d’aider les utilisateurs consiste à faire des recommandations. Le graphe des K-plus-proches-voisins (K-Nearest-Neighbours (KNN)) connecte chaque utilisateur aux k autres utilisateurs qui lui sont les plus similaires, étant donnée une fonction de similarité. Le temps de calcul d’un graphe KNN exact est prohibitif dans les services en ligne. Les approches existantes approximent l’ensemble de candidats pour chaque voisinage pour diminuer le temps de calcul. Dans cette thèse, nous poussons plus loin la notion d’approximation : nous approximons les données de chaque utilisateur, la similarité et la localité de données. L’approche obtenue est nettement plus rapide que toutes les autres.
Fichier principal
Vignette du fichier
RUAS_Olivier.pdf (2.3 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-01938076 , version 1 (28-11-2018)
tel-01938076 , version 2 (15-05-2019)

Identifiers

  • HAL Id : tel-01938076 , version 2

Cite

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

Share

Gmail Facebook Twitter LinkedIn More