Managing and mining data streams with evolving tuples
Institution:
NiceDisciplines:
Directors:
Abstract EN:
In this work, we present our study of the management and mining issues on data streams with evolving tuples. For instance, in an online auction system where bids on auction items are steaming, some users can be updated or revised in data streams. This kind of data streams is named Bi-streaming data in the thesis. We develop novel and efficient methods for managing and mining bi6streaming data. To model Bi-streaming data, we propose the Anti-Bouncing Streaming model (ABS). ABS enables methods for processing of data streams to handle tuple updates or revisions. To find frequent itemsets from B-streaming data over pane-based sliding windows, we provide theorems that can avoid re-scanning the past panes for possible frequent itemsets. We also design novel data structures and an efficient counting algorithm to get the counts for the candidate itemsets. To extract important feature set from data streams, based on ABS we devise a streaming feature set selection algorithm which is the first of its kind in the literature. This method is base upon information theory to extract the most informative feature set. To accelerate the extraction of the most informative feature set from high-dimensional data, we propose a framework than can reduces the huge search space to a rather small subset while still guarantee the quality of the discovered feature set. We have validated our method in a real-world dataset from France Telecom. Our techniques can be used in many applications such as on-line Web Analytics.
Abstract FR:
Depuis environ une décennie, le traitement des flux de données est nécessaire. Pendant ces dix années, les questions liées au traitement de flux de données ont été largement explorées. Récemment, au lieu de proposer des modèles généraux et des algorithmes, le traitement des flux de données s’oriente de plus en plus vers des tâches ou des domaines spécifiques. Dans cette thèse, nous présentons notre étude de la gestion et de la feuille de flux de données avec tuples évolutifs, c'est-à-dire avec des révisions du modèle. Par exemple, dans un système d’enchères en ligne où les offres sur les objets mis aux enchères sont en direct, il est possible que certains utilisateurs envoient plusieurs enchères pour un objet pendant un intervalle de temps spécifié. En conséquence, les données de l’utilisateur peuvent être mises à jour dans de telles applications. Les flux de données avec tuples évolutifs présentent de nouveaux défis. Dans ce travail, nous développons de nouveaux modèles pour la gestion et la fouille des flux de données avec des tuples évolutifs. Pour les données du modèle des flux avec tuples en évolutifs, nous proposons le modèle Anti-Bouncing Streaming (ABS) pour les flux d’usage. ABS traite les flux de données avec tuples évolutifs et il permet des méthodes de traitement des flux de données pour gérer les mises à jour ou les révisions. Pour trouver les motifs fréquents dans les flux de données avec les tuples évolutifs au cours sur les fenêtres coulissantes, nous procédons à l’analyse théorique et proposons des théorèmes qui peuvent éviter l’énumération et le scan de fenêtre pour vérifier les itemsets qui peuvent devenir fréquents. Nous concevons également des nouvelles structures de données qui peuvent gérer les flux de données avec les tuples évolutifs de manière efficace et faciliter l’extraction d’itemsets fréquents. Par ailleurs, nous élaborons un algorithme efficace de comptage pour vérifier la fréquence des itemsets candidats. Nous proposons également deux cadres applicatifs pour ce problème. Pour extraire des caractéristiques importantes du jeu flux de données (y compris celles avec des tuples en évolution), basée sur ABS, nous concevons un algorithme d’extraction de variables dans les flux qui est le premier dans la littérature. Cette méthode est basée sur la théorie de l’information pour en extraire les ensembles de variables informatifs. Pour accélérer encore l’extraction de l’ensemble de variables le plus informatif dans les données de grande dimension, nous proposons un cadre qui réduit l’espace de recherche pour un sous-ensemble assez petit tout en continuant à garantir la qualité des ensembles découverts. Nous avons validé nos méthodes sur des données du monde réel (France Télécom). Les expériences montrent que nos modèles et les méthodes sont efficaces. Nos techniques peuvent être utilisées dans de nombreuses applications telles que les Web Analytics en ligne dans les flux de données.