VOUZOUKIDOU Despoina

doctorant à Sorbonne Université
Équipe : BD
https://perso.lip6.fr/Nelly.Vouzoukidou

Direction de recherche : Bernd AMANN

Co-encadrement : CHRISTOPHIDES Vassilis

Evaluation Top-k de requêtes continues à large échelle

?1. Contexte :
Les technologies Web 2.0 ont transformé le web en un espace de partage d'information à large échelle où il est possible de suivre à la fois l'évolution des actualités à l'échelle mondiale et de partager des informations avec un groupe restreint d'amis dans un réseau social. La grande quantité et la "volatilité" des informations générées à travers les différents médias sociaux (Facebook, Twitter, blogs, forums de discussion) en association avec les médias d'informations traditionnelles (presse, télévision, radio) soulèvent des nouveaux défis dans l'agrégation et le traitement continue de flux d'informations.
Les agrégateurs de flux d'actualités (Google News, Yahoo! News ou MSNBC news) et de messages personnels (Google Blog Search ou Thoora) sont tous fondés des modèles et algorithmes des traitements efficace pour l'aggrégation et la personnalisation de l'information. L'agrégation consiste à rassembler les entités d'information (articles de news, messages d'utilisateurs) pour générer des rubriques d'informations avec des propriétés sémantiques partagés (articles concernant le même événement, messages Twitter sur un thème). Ces rubriques fournissent ainsi une vue abstraite et synthétique de l'information qui peut ensuite être personnalisée par rapport aux caractéristiques et aux besoins des utilisateurs. La personnalisation peut être explicite en sollicitant l'utilisateur de fournir un ensemble de mots-clés (pour la recherche) ou un feed-back (sur un résultat produit) ou implicite en prenant en compte son comportement (articles lus) ou son contexte social (liens sociaux dans un réseau social), géographique, matériel etc.
Étant donné le grand volume et la diversité des informations disponibles sur le Web 2.0, ainsi que le double rôle des utilisateurs comme producteurs et consommateurs d'informations, il existe un besoin vital pour des méthodes de filtrage efficaces capables de traiter et d'analyser un grand nombre de flux de données et de les adapter aux profiles évolutifs de millions d'utilisateurs.
2. Approche : évaluation de requêtes continues top-k
Le problème de la diffusion personnalisé d'informations a attiré l'attention du monde de la recherche et des grandes sociétés du web. Dans des systèmes commerciaux d'agrégation d'actualités comme Google News ou Yahoo! News, les articles sont regroupés en collections de rubriques thématiques qui sont ensuite ordonnées par leur importance (estimée par le débit des articles rentrants, le nombre de lecteurs, ...). Cette première phase d'édition est suivi de la phase de diffusion qui est généralement implantée par un service d'alertes indépendant qui traite les souscriptions et les profiles utilisateurs. La composition de ces deux phases simule essentiellement la fonctionnalité d'un système de requêtes continues à large échelle : chaque souscription d'un utilisateur correspond à une requête évaluée périodiquement par l'agregateur d'actualités, qui retrouve les résultats les plus pertinents et les délivre à l'utilisateur correspondant. Ce processus d'évaluation périodique devient rapidement inefficace pour le traitement d'un grand nombre de requêtes et oblige les systèmes de réduire la fréquence d'évaluation d'une requête particulière avec le risque de perte d'information.
Le sujet de thèse proposé concerne ce problème d'agrégation et de filtrage continu d'information d'un point de vue nouveau. Le point de départ principal est la nature continue des données ce qui nous mène naturellement à considérer les problèmes précédents comme un problème d'optimisation de requêtes continues top-k. Dans un tel contexte, un profil utilisateur est une requête continue combinée avec des fonctions de classement (ranking) appropriées pour calculer en continu les k rubriques les plus pertinents. Dans ce contexte, nous nous intéressons en particulier à des fonctions de classement qui prennent en compte à la fois l'importance globale des informations (par rapport aux autres informations et aux intérêts de tous les utilisateurs) et leur pertinence locale par rapport à un profil utilisateur donnée. L'importance d'une rubrique dépend du temps et de l'arrivée de nouveaux items qui peuvent accroître ou diminuer les scores d'une rubrique dans le temps et une difficulté nouvelle par rapport aux travaux existants (voir état de l'art plus loin) est la nature continue et non-monotone de ces fonctions qui résulte de la nature continue des données et du contexte.
Le problème de l'évaluation de requêtes top-k continues avec des fonctions hautement dynamiques et non-monotone n'a pas encore été exploré. L'objectif de cette thèse est de définir et d'implanter des algorithmes et structures de données pour traiter des grandes collections de requêtes continues sur des flux d'informations. En particulier, il faut définir un modèle de données et de requêtes approprié qui sera la base pour la résolution efficace de deux problèmes. Le premier problème consiste dans la sélection efficaces des requêtes concernées par l'arrivée d'une nouvelle entité d'information. Le processus de recherche est fondée sur des structures (indexes, tables inversées) qui permettent de réduire d'une manière optimale l'espace de recherche aux requêtes concernées par cette arrivée (dont les listes top-k seront affectées). Le deuxième problème consiste à maintenir les listes top-k d'une manière incrémentale sans recalculer les scores de toutes les réponses. La spécification et l'implantation de ce processus doit passer à l'échelle à la fois dans la fréquence d'arrivée de nouvelles entités d'information et dans le nombre de requêtes. Un défi important sera l'étude du compromis entre l'espace occupé, le temps de recherche et le temps de maintenance des structures d'index sous-jacent.
État de l'art :
Le problème du classement d'actualités a déjà attiré l'attention de multiples travaux de recherche. La plupart des études mesurent l'importance et la pertinence d'actualités en considérant l'intérêt des utilisateurs et l'attention médiatique aux actualités [1], l'autorité des sources [2], la nouveauté des articles [3) et les préférences des utilisateurs [4]. Ces travaux sont fondés sur l'agrégation thématique d'articles pour mesurer l'importance et sur les modèles de décroissance temporelle (decay) qui capturent les variations temporelle de l'information. [5] s'adresse au problème de recherche top-k de clusters dans le contexte de requêtes non-continues (snapshot), tandis que [6] et [7] sont les seuls travaux qui s'intéressent à l'évaluation de requêtes continues sur des flux d'informations textuels. Les travaux [8] et [9] s'adressent à des problèmes similaire dans le contexte de données relationnel avec un nombre de dimensions. plus faible Malgré cet intérêt important dans le classement d'informations, il n'existe pas de travaux qui s'intéressent à la fois au classement d'informations textuels agrégées avec des fonctions de scores dynamiques.
Ce travail de thèse profitera des résultats du projet ANR RoSeS et sera dirigé en collaboration avec Vassilis Christophides de l'Université de Crète.
Références
[1] Canhui Wang, Min Zhang, Liyun Ru, and Shaoping Ma. Automatic online news topic ranking using media focus and user attention based on aging theory. In Proceeding of the 17th ACM conference on Information and knowledge management, CIKM ’08, pages 1033–1042, New York, NY, USA, 2008. ACM.
[2] Gianna M. Del Corso, Antonio Gull´?, and Francesco Romani. Ranking a stream of news. In Proceedings of the 14th international conference on World Wide Web, WWW ’05, pages 97–106, New York, NY, USA, 2005. ACM.
[3] Evgeniy Gabrilovich, Susan Dumais, and Eric Horvitz. Newsjunkie: providing personalized newsfeeds via analysis of information novelty. In Proceedings of the 13th international conference on World Wide Web, WWW ’04, pages 482–490, New York, NY, USA, 2004. ACM.
[4] Abhinandan S. Das, Mayur Datar, Ashutosh Garg, and Shyam Rajaram. Google news personalization: scalable online collaborative filtering. In Proceedings of the 16th international conference on World Wide Web, WWW ’07, pages 271–280, New York, NY, USA, 2007. ACM.
[5] Manish Bhide, Venkatesan T. Chakaravarthy, Krithi Ramamritham, and Prasan Roy. Keyword search over dynamic categorized information. ICDE 2009. Shanghai, China
[6] Parisa Haghani, Sebastian Michel, and Karl Aberer. The gist of everything new: personalized top-k processing over web 2.0 streams. In Proceedings of the 19th ACM international conference on Information and knowledge management, CIKM ’10, pages 489–498, New York, NY, USA, 2010. ACM.
[7] Kyriakos Mouratidis and HweeHwa Pang. An incremental threshold method for continuous text search queries. Data Engineering, International Conference on, 0:1187–1190, 2009.
[8] Gautam Das, Dimitrios Gunopulos, Nick Koudas, and Nikos Sarkas. Ad-hoc top-k query answering for data streams. In Proceedings of the 33rd international conference on Very large data bases, VLDB ’07, pages 183–194. VLDB Endowment, 2007.
[9] Kyriakos Mouratidis, Spiridon Bakiras, and Dimitris Papadias. Continuous monitoring of top-k queries over sliding windows. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data, SIGMOD’06, pages 635–646, New York, NY, USA, 2006. ACM.

Soutenance : 17/09/2015

Membres du jury :

Mme. Evaggelia Pitoura, Professeur, University of Ioannina [Rapporteur]
Mme Sihem Amer-Yahia, Directrice de Recherche, Laboratoire d’Informatique de Grenoble [Rapporteur]
M. Bernd Amann, Professeur, Université Pierre & Marie Curie
M. Vassilis Christophides, Professeur, University of Crete
M. Themis Palpanas, Professeur, LIPADE - Paris Descartes Univ.
M. Dan Vodislav, Professeur, Université de Cergy-Pontoise
M. Ludovic Denoyer, Professeur, Université Pierre & Marie Curie

Date de départ : 31/12/2015

Publications 2012-2016