ASAP – As Scalable As Possible

(French version below)

You are cordially invited to attend the PhD defense of Stéphane Delbruel that will be held on January 27, 2017 at 14:00 in room Métivier and for a drink in room Sein.

Jury members:
Romain Rouvoy, Professor at the University of Lille
Danny Hughes, Professor at the Catholic University of Leuven
Antonio Carzaniga, Professor at the Università della Svizzera italiana
Sonia Ben Mokhtar, CNRS researcher at the LIRIS lab, Villeurbanne
Guillaume Pierre, Professor at the University of Rennes 1
François Taiani, Professor at the University of Rennes 1
Davide Frey, Researcher at Inria Rennes Bretagne-Atlantique

Title: Towards an Architecture for Tag-based Predictive Placement in Distributed Storage Systems

Abstract:
This thesis gathers and presents the most important part of the research we carried out over the last few years on decentralised storage systems. In this thesis, we argue that user-generated meta-data in fully distributed user-generated- content systems constitute a reliable source to determine where uploaded content will be consumed in the future. This makes it possible to predictively place this content close to future consumers, thereby maximizing the suitability of proximity caches.

Vous êtes cordialement invités à venir assister à la soutenance de thèse de Stéphane Delbruel qui se tiendra vendredi 27 janvier à 14h en salle Métivier ainsi qu’au pot qui suivra en salle Sein.

Composition du jury :
Romain Rouvoy, Professeur à l’Université de Lille
Danny Hughes, Professeur à l’Université catholique de Louvain
Antonio Carzaniga, Professeur à l’Université de la Suisse italienne, Lugano
Sonia Ben Mokhtar, Chargé de recherche CNRS au LIRIS, Villeurbanne
Guillaume Pierre, Professeur à l’Université Rennes 1
François Taiani, Professeur à l’Université Rennes 1
Davide Frey, Chargé de recherche à Inria Rennes Bretagne-Atlantique

Titre : Vers une architecture pour le placement prédictif dans les systèmes de stockage distribué

Résumé :
Cette thèse rassemble et présente la part plus importante de mes recherches durant ces dernières années, portant sur les systèmes de stockage décentralisés. Dans cette thèse, nous affirmons que les méta-données générées par les utilisateurs dans les systèmes pleinement distribués de gestion de contenu généré par les utilisateurs représentent une source d’informations fiable nous permettant de déterminer lors de la mise en ligne d’un contenu, où il sera consommé dans le futur. Cela rend donc possible le placement prédictif de contenus proche de ses futurs consommateurs, augmentant par là même la pertinence des caches de proximité.

(French version below)

You are cordially invited to attend the PhD defense of Javier Olivares that will be held on December 19, 2016 at 14:30 in room Petri-Turing and for a drink in room Minquiers.

Jury members:
Pierre Sens, Professor, University of Paris 6
Sébastien Monnet, Professor, University of Savoie Mont Blanc
Erwan Le Merrer, Senior Scientist, Technicolor
François Taiani, Professor, University of Rennes 1
Anne-Marie Kermarrec, Supervisor, Inria

Title: Scaling out-of-core K-Nearest Neighbors Computation on Single Machines

Abstract:
The K-Nearest Neighbors (KNN) is an efficient method to find similar data among a large set of it. Over the years, a huge number of applications have used KNN’s capabilities to discover similarities within the data generated in diverse areas such as business, medicine, music, and computer science. Despite years of research have brought several approaches of this algorithm, its implementation still remains a challenge, particularly today where the data is growing at unthinkable rates. In this context, running KNN on large datasets brings two major issues: huge memory footprints and very long runtimes. Because of these high costs in terms of computational resources and time, KNN state-of the-art works do not consider the fact that data can change over time, assuming always that the data remains static throughout the computation, which unfortunately does not conform to reality at all.
In this thesis, we address these challenges in our contributions. Firstly, we propose an out-of-core approach to compute KNN on large datasets, using a commodity single PC. We advocate this approach as an inexpensive way to scale the KNN computation compared to the high cost of a distributed algorithm, both in terms of computational resources as well as coding, debugging and deployment effort. Secondly, we propose a multithreading out-of-core approach to face the challenges of computing KNN on data that changes rapidly and continuously over time.
After a thorough evaluation, we observe that our main contributions address the challenges of computing the KNN on large datasets, leveraging the restricted resources of a single machine, decreasing runtimes compared to that of the baselines, and scaling the computation both on static and dynamic datasets.

Vous êtes cordialement invités à venir assister à la soutenance de thèse de Javier Olivares qui se tiendra lundi 19 décembre à 14h30 en salle Petri-Turing ainsi qu’au pot qui suivra en salle Minquiers.

Composition du jury :
Pierre Sens, Professeur, Université de Paris 6
Sébastien Monnet, Professeur, Université Savoie Mont Blanc
Erwan Le Merrer, Chargé de recherche, Technicolor
François Taiani, Professeur, Université de Rennes 1
Anne-Marie Kermarrec, Directrice de thèse, Inria

Titre : Faire passer à l’échelle le calcul “out-of-core” des K-plus proche voisins sur une seule machine

Résumé :
La technique des K-plus proches voisins (K-Nearest Neighbors (KNN) en Anglais) est une méthode efficace pour trouver des données similaires au sein d’un grand ensemble de données. Au fil des années, un grand nombre d’applications ont utilisé les capacités du KNN pour découvrir des similitudes dans des jeux de données de divers domaines tels que les affaires, la médecine, la musique, ou l’informatique. Bien que des années de recherche aient apporté plusieurs approches de cet algorithme, sa mise en œuvre reste un défi, en particulier aujourd’hui alors que les quantités de données croissent à des vitesses inimaginables. Dans ce contexte, l’exécution du KNN sur de grands ensembles pose deux problèmes majeurs : d’énormes empreintes mémoire et de très longs temps d’exécution. En raison de ces coût élevés en termes de ressources de calcul et de temps, les travaux de l’état de l’art ne considèrent pas le fait que les données peuvent changer au fil du temps, et supposent toujours que les données restent statiques tout au long du calcul, ce qui n’est malheureusement pas du tout conforme à la réalité.
Nos contributions dans cette thèse répondent à ces défis. Tout d’abord, nous proposons une approche out-of-core pour calculer les KNN sur de grands ensembles de données en utilisant un seul ordinateur. Nous préconisons cette approche comme un moyen moins coûteux pour faire passer à l’échelle le calcul des KNN par rapport au coût élevé d’un algorithme distribué, tant en termes de ressources de calcul que de temps de développement, de débogage et de déploiement. Deuxièmement, nous proposons une approche out-of-core multithreadée (i.e. utilisant plusieurs fils d’exécution) pour faire face aux défis du calcul des KNN sur des données qui changent rapidement et continuellement au cours du temps.
Après une évaluation approfondie, nous constatons que nos principales contributions font face aux défis du calcul des KNN sur de grands ensembles de données, en tirant parti des ressources limitées d’une machine unique, en diminuant les temps d’exécution par rapport aux performances actuelles, et en permettant le passage à l’échelle du calcul, à la fois sur des données statiques et des données dynamiques.

(French version below)

Note: A video recording of the defense as well as the slides of the presentation can be found here.

You are cordially invited to attend the thesis defense of Nupur Mittal that will be held Friday November 25, 2016 at 14:30 in room Petri-Turing and for a drink in room Minquiers.

Jury members:
Pascal Molli, Professor, University of Nantes
Esther Pacitti, Professor, University of Montpellier 2
David Gross-Amblard, Professor, University of Rennes 1
Erwan Le Merrer, Senior Scientist, Technicolor
George Giakkoupis, Researcher, Inria Rennes Bretagne-Atlantique
Anne-Marie Kermarrec, Supervisor, Mediego

Title: Data, Learning and Privacy in Recommendation Systems

Abstract:
Recommendation systems have gained tremendous popularity, both in academia and industry. They have evolved into many different varieties depending mostly on the techniques and ideas used in their implementation. This categorization also marks the boundary of their application domain. Regardless of the types of recommendation systems, they are complex and multi-disciplinary in nature, involving subjects like information retrieval, data cleansing and preprocessing, data mining etc. In our work, we identify three different challenges (among many possible) involved in the process of making recommendations and provide their solutions.
We elaborate the challenges involved in obtaining user-demographic data, and processing it, to render it useful for making recommendations. The focus here is to make use of Online Social Networks to access publicly available user data, to help the recommendation systems. Using user-demographic data for the purpose of improving the personalized recommendations, has many other advantages, like dealing with the famous cold-start problem. It is also one of the founding pillars of hybrid recommendation systems. With the help of this work, we underline the importance of user’s publicly available information like tweets, posts, votes etc. to infer more private details about her.
As the second challenge, we aim at improving the learning process of recommendation systems. Our goal is to provide a k-nearest neighbor method that deals with very large amount of datasets, surpassing billions of users. We propose a generic, fast and scalable k-NN graph construction algorithm that improves significantly the performance as compared to the state-of-the art approaches. Our idea is based on leveraging the bipartite nature of the underlying dataset, and use a preprocessing phase to reduce the number of similarity computations in later iterations. As a result, we gain a speed-up of 14 compared to other significant approaches from literature.
Finally, we also consider the issue of privacy. Instead of directly viewing it under trivial recommendation systems, we analyze it on Online Social Networks. First, we reason how OSNs can be seen as a form of recommendation systems and how information dissemination is similar to broadcasting opinion/reviews in trivial recommendation systems. Following this parallelism, we identify privacy threat in information diffusion in OSNs and provide a privacy preserving algorithm for the same. Our algorithm Riposte quantifies the privacy in terms of differential privacy and with the help of experimental datasets, we demonstrate how Riposte maintains the desirable information diffusion properties of a network.

Note: Un enregistrement vidéo de la soutenance ainsi que le support de la présentation sont disponibles ici.

Vous êtes cordialement invités à venir assister à la soutenance de thèse de Nupur Mittal qui se tiendra vendredi 25 novembre à 14h30 en salle Petri-Turing ainsi qu’au pot qui suivra en salle Minquiers.

Composition du jury :
Pascal Molli, Professeur, Université de Nantes
Esther Pacitti, Professeur, Université de Montpellier 2
David Gross-Amblard, Professeur, Université de Rennes 1
Erwan Le Merrer, Chargé de recherche, Technicolor
George Giakkoupis, Chargé de recherche, Inria Rennes Bretagne-Atlantique
Anne-Marie Kermarrec, Directrice de thèse, Mediego

Titre : Données, apprentissage et respect de la vie privée dans les systèmes de recommandation

Résumé :
Les systèmes de recommandation sont devenus une partie indispensable des services et des applications d’internet, en particulier dû à la surcharge de données provenant de nombreuses sources. Quel que soit le type, chaque système de recommandation a des défis fondamentaux à traiter. Dans ce travail, nous identifions trois défis communs, rencontrés par tous les types de systèmes de recommandation : les données, les modèles d’apprentissage et la protection de la vie privée. Nous élaborons différents problèmes qui peuvent être créés par des données inappropriées en mettant l’accent sur sa qualité et sa quantité. De plus, nous mettons en évidence l’importance des réseaux sociaux dans la mise à disposition publique de systèmes de recommandation contenant des données sur ses utilisateurs, afin d’améliorer la qualité des recommandations. Nous fournissons également les capacités d’inférence de données publiques liées à des données relatives aux utilisateurs. Dans notre travail, nous exploitons cette capacité à améliorer la qualité des recommandations, mais nous soutenons également qu’il en résulte des menaces d’atteinte à la vie privée des utilisateurs sur la base de leurs informations. Pour notre second défi, nous proposons une nouvelle version de la méthode des k plus proches voisins (knn, de l’anglais k-nearest neighbors), qui est une des méthodes d’apprentissage parmi les plus populaires pour les systèmes de recommandation. Notre solution, conçue pour exploiter la nature bipartie des ensembles de données utilisateur-élément, est évolutive, rapide et efficace pour la construction d’un graphe knn et tire sa motivation de la grande quantité de ressources utilisées par des calculs de similarité dans les calculs de knn. Notre algorithme KIFF utilise des expériences sur des jeux de données réelles provenant de divers domaines, pour démontrer sa rapidité et son efficacité lorsqu’il est comparé à des approches issues de l’état de l’art. Pour notre dernière contribution, nous fournissons un mécanisme permettant aux utilisateurs de dissimuler leur opinion sur des réseaux sociaux sans pour autant dissimuler leur identité. Notre algorithme Riposte est un algorithme réparti pour la diffusion d’informations (idées, nouvelles, opinions ou tendances) dans un réseau social. Il assure également qu’une information ne se répand largement que si (et seulement si) une grande partie des utilisateurs trouvent qu’elle est intéressante. En outre, si seulement quelques utilisateurs pensent qu’une information est intéressante, Riposte fait en sorte que le processus de diffusion de l’information meurt rapidement, pour limiter sa diffusion, et tout cela se fait dans le respect de la vie privée des utilisateurs. Chacune de nos contributions, ainsi que leurs fondements théoriques, est soutenue par des expériences utilisant des ensembles de données réelles et variées.