Université de Rennes 1 The many faces of approximation in KNN graph computation Les multiples facettes des approximations dans la construction de graphes KN graphe KNNapprentissageBase de donnéesRecommandations KNN graphMachine learningDatabaseRecommendations Apprentissage automatiqueThèses et écrits académiques Approximation, Théorie de l'Thèses et écrits académiques Systèmes de recommandation (informatique)Thèses et écrits académiques 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. 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. Electronic Thesis or DissertationText en application/pdf1 : 2357 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/2c8140ee-ce68-4774-b182-85342b4d4b4e Ruas Olivier 1989-04-30 FR 235831972 olivier.ruas@gmail.com 2018REN1S088 http://www.theses.fr/2018REN1S088 2018-12-17 Informatique Universite de Rennes 1thesis.degree.grantor_1 02778715X Doctorat non ouiTaïaniFrançoisintervenant_1081430264KermarrecAnne-Marieintervenant_2110336143 MATHSTICecoleDoctorale_1 204770424 Universite Bretagne LoirepartenaireRecherche_1 191639044 INRIA-RENNES partenaireRecherche_2 133175863 ddc:004 TaïaniFrançoisKermarrecAnne-MarieUniversite de Rennes 1Sciences et technologie, medecine, pharmacie, odontologie, droit, economie, gestion, philosophieMATHSTICÉcole doctorale Mathématiques et sciences et technologies de l'information et de la communication (Rennes)Universite Bretagne Loire Communaute des etablissements d enseignement superieur et de recherche (ComuE) INRIA-RENNES ASCII PDF 2413859