Giant components on data streams

Nous étudions des données de nature diverse sous forme de flux, en particulier: • Base de données,• Réseaux sociaux, • Données de texte. Pour une base de données qui suit un schéma relationnel, un schéma d’analyse OLAP (Online Analytical Processing) définit une des tables de la base de données comme une table d’analyse. Nous supposons que les tuples de la table d'analyse arrivent sous forme d’un flux. Nous étudions l’approximation des requêtes OLAP, en échantillonnant de manière non uniforme les tuples du flux sans stocker les données d’analyse et donnons un modèle de préférence dans ce cadre. Dans le cas du réseau social Twitter, nous observons un flux de tweets qui contiennent un tag donné et le transformons en un flux d’arêtes d’un graphe. Nous souhaitons étudier l’existence des grands clusters dans le graphe ainsi obtenu. Nous proposons une méthode d’échantillonnage uniforme qui va associer au graphe un sous-graphe aléatoire et étudions les composantes géantes de ce sous-graphe aléatoire comme témoin des grands clusters du graphe d’origine. Pour un flux de texte, nous considérons les paires de mots dans une phrase lemmatisée comme des arêtes d’un graphe où les nœuds sont les mots. Nous transformons le flux de texte en flux d’arêtes. Nous échantillonnons les arêtes proportionnellement à la similarité Word2vec des mots. Nous analysons ensuite les composantes géantes. Nous étendons les vecteurs Word2vec en prenant en compte la morphologie d'une langue, en particulier la structure des préfixes et des suffixes d'un mot. Les nouveaux vecteurs d'un mot ont 3 composantes : un vecteur pour le préfixe, un vecteur pour la racine et un vecteur pour le suffixe. Nous définissons un vecteur probabiliste pour les phrases. Sur les trois types de données, nous avons échantillonné selon des distributions précises. Les résultats principaux de cette thèse montrent comment approcher les propriétés de ces données avec ces échantillons.We study deferent types of data as a stream:• Databases, • Social Networks,• Text data. For a database that follows a relational schema, an OLAP (Online Analytical Proces-sing) analysis schema defines one of the database tables as an analysis table. We supposethat the tuples of the analysis table arrive as a stream. We study the approximation ofOLAP queries, by sampling with weights the tuples of the stream without storing the analysis data. We give a preference model in this context. For the social network Twitter, we observe a stream of tweets that contain any giventag and transform it into a stream of edges of a graph. We study the existence of large clusters in the generated graph. We propose a uniform sampling method that will associatea random subgraph of the graph and study the giant components of this random subgraphas a witness of the large clusters of the original graph. For a stream of text, we consider the pairs of words in a lemmatized sentence as edgesof a graph where the nodes are the words. We transform the stream of text into a stream of edges. We sample the edges proportionally to the Word2vec similarity of the words. We then analyze the giant components. We extend the classical Word2vec vectors, in order to take into account the morphology of the words, i.e. the prefixes, roots and suffixes. A new vector has 3 components, one for the prefix, one for the root and one for the suffix. We define a probabilistic vector associated with the sentences. With the three types of data, we sampled according to speci_c distributions. The main results of this thesis show how the properties of these data can be approximated with these samples