Continuous processing of top-k queries in social networks

En raison du grand succès des réseaux sociaux, la nature et mode de diffusion del’information sur le Web a changé en faveur de contenus dynamiques diffusés sousforme de flux d’information. Dans le contexte des réseaux sociaux, les utilisateurs peuvent s’abonner à de multiples sources d’information et recevoir continuellement de nouveaux contenus. Or, ce nouveau mode de publication/consommation peut entraîner d’énormes quantités d’information, en surchargeant les utilisateurs. Ainsi,il est essentiel de développer des techniques efficaces de filtrage et de classement qui permettent aux utilisateurs d’être efficacement mis à jour avec le contenu le plus intéressant.Les requêtes top-k sur les flux d’information limitent les résultats au contenu le plus pertinent. Pour améliorer la pertinence des résultats, le modèle de classement des résultats de requêtes devrait tenir compte de divers facteurs de contexte, y compris les facteurs traditionnels basés sur le contenu, les facteurs liés aux utilisateurs et leurs relations (réseau social). Dans le réseau social, le maintien des ensembles de top-k peut être plus difficile car de nombreux événements pourraient changer les messages de top-k tels que le nouveau message, la nouvelle action, le nouvel utilisateur, les modifications de profil, etc. Pour un grand réseau social avec des millions d’utilisateurs et des milliards de messages, le traitement continu des requêtes top-k est l’approche la plus efficace. Cependant, les systèmes actuels pour le traitementcontinu des requêtes top-k échouent lorseque ces systèmes considèrent des modèles de classement riches avec des critères de réseau social. En outre, de tels systèmes ne tiennent pas compte de la diversité des contenus publiés.Dans cette thèse, nous nous concentrons sur le filtrage des flux d’information basé sur le calcul des messages top-k pour chaque utilisateur dans le réseau social. Nous visons à développer un système à large échelle capable d’évaluer efficacement les requêtes top-k continues avec une fonction de classement complexe. Nous proposons l’algorithme SANTA, capable de gérer des fonctions de classement complexes avec des critères sociaux tout en maintenant un traitement continu des requêtes top-k. Nous proposons aussi une variante (SANTA +) qui accélère le traitement d’actions dans les réseaux sociaux. Pour tenire compte de la diversité des contenus publiés, nous proposons l’algorithme DA-SANTA qui étend l’algorithme SANTA pour intégrer la diversité dans le modèle top-k continu tout en maintenant l’efficacité du système. Nos expérimentation sont menées sur des données réelles extraite de Twitter, illustrant les propriétés de nos algorithmes et de montrer leur efficacité.Information streams provide today a prevalent way of publishing and consuming content on the Web, especially due to the great success of social networks. In the social networks context, users may subscribe to several information sources of interest and continuously receive new published content. But, this new publishing/consumption mode may lead to huge amounts of received information, overwhelming for human processing. Thus, there is a vital need to develop effective filtering and ranking techniques which allow users to efficiently be updated with the most interesting content. Top-k queries over the streams of interest allow limiting results to the most relevant content. To provide a relevant content, the ranking model should consider various context factors including traditional IR factors and social network. In the social network, maintaining top-k sets may be more difficult because many events could produce changes in the top-k sets such as new message, new action, new user, profile changes, etc. For a large social network with millions of users and billionsof messages, the continuous processing of the top-k queries is the most effective approach. However, current systems fail in combining continuous top-k processing with rich scoring models including social network criteria. Moreover, such systems do not consider the diversity of published content.In this thesis, we focus on filtering information streams based on the computation of top-k messages for each user in the social network. We aim to develop a scalable system that be able to efficiently evaluate the continuous top-k queries using the continuous approach with a ranking function including social network criteria. We propose the SANTA algorithm, able to handle scoring functions including content similarity but also social network criteria and events in a continuous processing of top-k queries. We propose a variant (SANTA+) that accelerates the processing of interaction events in social networks. To provide both diverse and relevant messages in top-k sets, we propose the DA-SANTA algorithm which extends the SANTA algorithm to integrate the diversity into the continuous top-k model while maintaining the efficiency of the system. Our experiments are conducted over a real data-set extracted from Twitter, illustrating the properties of our algorithms and demonstrating their efficiency