Master 2013 2014
Stages de la spécialité SAR
An Intelligent Publish/Subscribe System at Web Scale


Site :Vertigo
Lieu :Laboratoire CEDRIC/CNAM
Encadrant : Cedric du Mouza Nicolas Travers
Dates :01/03/2014 au 31/08/2014
Rémunération :436€/mois
Mots-clés : Parcours SAR autre qu’ATIAM, rech./prof., Parcours SAR, aussi pour STL

Description

Internet est aujourd’hui un support économique reconnu et utilisé pour la diffusion d’informations à large échelle. Afin de réduire l’intervalle de temps nécessaire entre la publication de l’information sur un site web ou un réseau social et sa consultation par les utilisateurs, les systèmes de notifications en continu ont pris une ampleur considérable sur la toile. L’approche « publication/souscription » (Pub/Sub) [3] pour la diffusion contrôlée et efficace d’informations sur le web est devenue la référence du domaine de notification en continue. Les fournisseurs d’information diffusent l’apparition de nouvelles informations (par exemple un article dans un journal électronique) à travers entre autres des flux (feeds) RSS [1] ou ATOM [2] auxquels les clients intéressés peuvent s’abonner grâce à des portails web ou des logiciels (lecteurs RSS/ATOM) spécialisés. Ce processus permet au final à chaque utilisateur de surveiller « en temps réel » l’évolution d’informations publiées sur le Web. Naturellement, le nombre de ces sources de données grandit chaque jour et le nombre d’utilisateurs explose (e.g., Twitter suit une croissance exponentielle). De fait, le passage à l’échelle des systèmes de notification de type « publication/souscription » est un défi réel aussi bien au niveau qualitatif que quantitatif. En effet, il faut traiter un énorme volume de données en continue, tout en étant capable de délivrer des informations pertinentes à un nombre d’utilisateurs toujours plus grand, sans les submerger d’informations hors sujet ou redondantes. Les portails d’agrégation spécialisés comme Blastfeed.com, Plazoo.com et Technorati.com sont de plus en plus confrontés à des problèmes de passage à l’échelle et proposent uniquement des possibilités de filtrages rudimentaires pour l’utilisateur. Nous avons réalisé une étude préliminaire approfondie du comportement des flux RSS, dans laquelle nous nous sommes particulièrement intéressé à leur comportement et à la structure et contenu des items publiés [4]. En nous appuyant sur cette étude, nous avons proposé des structures d’indexation de souscriptions (requêtes utilisateurs) basées sur des mots-clés et adaptées à la notification de messages en continu [5]. Toutefois, malgré cette étape de filtrage par mots-clés qui permet de réduire le nombre de messages notifiés aux utilisateurs, la masse d’information reste phénoménale. De fait, l’utilisateur reste submergé par des informations redondantes ou largement similaires. Ainsi, nous souhaitons étudier une nouvelle approche de filtrage intelligent, complémentaire des travaux précédents, reposant sur la diversité et la nouveauté des résultats sur des données produites en continu [6,7,8]. L’idée est que les messages déjà notifiés (l’historique de la souscription) à un utilisateur peuvent servir de filtre pour les messages futurs. Les notions de nouveauté (information non encore notifiée dans l’historique) et de diversité (information globalement différente de l’historique) sont les concepts clés sur lesquels repose ce sujet de thèse. Sujet de stage : Ce stage a pour but de faire la continuité de la thèse de Zeinab Hmedeh qui vient d’être soutenue qui a ouvert de nouvelles pistes de recherche, aussi bien sur des points d’optimisation que sur le périmètre d’étude à développer. Deux axes principaux nous intéressent donc dans ce stage : 1) Le passage à l’échelle du web pour notre système de notification. En effet, celui-ci a été jusqu’ici implémentée en mémoire centrale pour des raisons d’efficacité, et nous souhaiterions pouvoir repenser celui-ci dans un contexte distribué. Cela pose de nombreux problèmes de segmentation et de répartition qui se retrouvent à plusieurs endroits de notre système. Cela peut également concerner les deux parties distinctes de notre système pour rapprocher sémantiquement les notifications éventuelles entre les étapes de matching et de filtrage. Ces techniques de distribution reposeront sur le Consistent Hashing et les systèmes basés sur la distribution massive de données [10, 11, 12, 13, 14, 15]. 2) Proposer une optimisation significative et évolutive de notre système de filtrage par nouveauté et diversité pour factoriser les historiques locaux. En effet, lors de notre étape de filtrage, de nombreuses souscriptions partages des historiques locaux fortement similaires. Leur traitement étant actuellement indépendant, une factorisation des historiques permettrait de ne faire qu’un seul traitement et de réduire considérablement les temps de traitement dans le système. Toutefois, la factorisation de plusieurs historiques dépendent essentiellement des items notifiés à un instant t. De fait, cette factorisation ne peut fonctionner que durant un laps de temps où le contenu des informations convergent sur un même sujet. Ils peuvent évoluer avec le temps. Cette technique de factorisation devra donc être évolutive pour pouvoir garantir une qualité de service à l’utilisateur. Nous devrons comparer notre approche avec des techniques de scoring en requêtes Top-K [9] qui factorisent les intérêts plutot que le contenu notifié. Ces deux sujets peuvent aboutir à un sujet de thèse au niveau de l’ouverture que ceux-ci donne en perspective. Ils permettront par ailleurs de donner un nouveau départ à la collaboration entre les deux équipes ISID et Vertigo sur un sujet qui a donné lieu à de nombreuses publications et qui est très prometteur dans le cadre de nouveaux projets de recherche.

Bibliographie

[1] RSS. Really Simple Syndication. http://www.rssboard.org/rss-specifi... [2] Atom. W3C. Atomenabled. http://www.atomenabled.org/.

[3] "Distributed Event-Based Systems", 2007 by Gero Muehl, Ludger Fiege, and Peter R. Pietzuch, Springer-Verlag, Germany.

[4] Z. Hmedeh, N. Travers, N. Vouzoukidou, V. Christophides, C. du Mouza, M. Scholl - Characterizing Web Syndication Behavior and Content, WISE’11, The 12th International Conference on Web Information System Engineering, October 2011, pp.29—42, Series LNCS, Sidney, Australia

[5] Z. Hmedeh, H. Kourdounakis, V. Christophides, C. du Mouza, M. Scholl, N. Travers - Subscription Indexes for Web Syndication Systems , International Conference on Extending Database Technology (EDBT’12), March 2012, pp.311-322, Berlin, Germany

[6] M. Drosou, E. Pitoura – Dynamic Diversification of Continuous Data. EDBT 2012, Berlin, Germany

[7] Marcos R. Vieira, Humberto L. Razente, Maria C. N. Barioni, Marios Hadjieleftheriou, Divesh Srivastava, Caetano Traina Jr., Vassilis J. Tsotras – On Query Result Diversification. ICDE 2011

[8] A. Angel, N. Koudas – Efficient Diversity-Aware Search. SIGMOD 2011, Athens, Greece

[9] N. Vouzoukidou, B. Amann, V. Christophides - Processing continuous text queries featuring non-homogeneous scoring functions. CIKM 2012 : 1065-1074

[10] Brad Fitzpatrick. 2004. Distributed caching with memcached. Linux J. 2004, 124 (August 2004) [11] T. White. 2009. Hadoop : The Definitive Guide. O’Reilly Media, Inc. June 2009. [12] Apache Hadoop. http://hadoop.apache.org/. [13] Pig. Hadoop data-flow platform. http://pig.apache.org/

[14] Ashish Thusoo, Joydeep Sen Sarma, Namit Jain, Zheng Shao, Prasad Chakka, Suresh Anthony, Hao Liu, Pete Wyckoff, and Raghotham Murthy. 2009. Hive : a warehousing solution over a map-reduce framework. Proc. VLDB Endow. 2, 2 (August 2009), 1626-1629

[15] Hbase. http://hbase.apache.org/