Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les capteurs multi- et hyper-spectraux génèrent un énorme flot de données. Un moyende contourner cette difficulté est de pratiquer une acquisition compressée de l'objet multi- ethyper-spectral. Les données sont alors directement compressées et l'objet est reconstruitlorsqu'on en a besoin. L'étape suivante consiste à éviter cette reconstruction et à travaillerdirectement avec les données compressées pour réaliser un traitement classique sur un objetde cette nature. Après avoir introduit une première approche qui utilise des outils riemannienspour effectuer une détection de contours dans une image multispectrale, nous présentonsles principes de l'acquisition compressée et différents algorithmes utilisés pour résoudre lesproblèmes qu'elle pose. Ensuite, nous consacrons un chapitre entier à l'étude détaillée de l'und'entre eux, les algorithmes de type Bregman qui, par leur flexibilité et leur efficacité vontnous permettre de résoudre les minimisations rencontrées plus tard. On s'intéresse ensuiteà la détection de signatures dans une image multispectrale et plus particulièrement à unalgorithme original du Guo et Osher reposant sur une minimisation L1. Cet algorithme estgénéralisé dans le cadre de l'acquisition compressée. Une seconde généralisation va permettrede réaliser de la détection de motifs dans une image multispectrale. Et enfin, nous introduironsde nouvelles matrices de mesures qui simplifie énormément les calculs tout en gardant debonnes qualités de mesures. / Multi- and hyper-spectral sensors generate a huge stream of data. A way around thisproblem is to use a compressive acquisition of the multi- and hyper-spectral object. Theobject is then reconstructed when needed. The next step is to avoid this reconstruction and towork directly with compressed data to achieve a conventional treatment on an object of thisnature. After introducing a first approach using Riemannian tools to perform edge detectionin multispectral image, we present the principles of the compressive sensing and algorithmsused to solve its problems. Then we devote an entire chapter to the detailed study of one ofthem, Bregman type algorithms which by their flexibility and efficiency will allow us to solvethe minimization encountered later. We then focuses on the detection of signatures in amultispectral image relying on an original algorithm of Guo and Osher based on minimizingL1. This algorithm is generalized in connection with the acquisition compressed. A secondgeneralization will help us to achieve the pattern detection in a multispectral image. Andfinally, we introduce new matrices of measures that greatly simplifies calculations whilemaintaining a good quality of measurements.

Internet est une source infinie de données émanant de sources telles que les réseaux sociaux ou les capteurs (domotique, ville intelligente, véhicule autonome, etc.). Ces données hétérogènes et de plus en plus volumineuses, peuvent être gérées grâce au web sémantique, qui propose de les homogénéiser et de les lier et de raisonner dessus, et aux systèmes de gestion de flux de données, qui abordent essentiellement les problèmes liés au volume, à la volatilité et à l’interrogation continue. L’alliance de ces deux disciplines a vu l’essor des systèmes de gestion de flux de données sémantiques RSP (RDF Stream Processing systems). L’objectif de cette thèse est de permettre à ces systèmes, via de nouvelles approches et algorithmes à faible coût, de rester opérationnels, voire plus performants, même en cas de gros volumes de données en entrée et/ou de ressources système limitées.Pour atteindre cet objectif, notre thèse s’articule principalement autour de la problématique du : "Traitement de flux de données sémantiques dans un contexte de systèmes informatiques à ressources limitées". Elle adresse les questions de recherche suivantes : (i) Comment représenter un flux de données sémantiques ? Et (ii) Comment traiter les flux de données sémantiques entrants, lorsque leurs débits et/ou volumes dépassent les capacités du système cible ?Nous proposons comme première contribution une analyse des données circulant dans les flux de données sémantiques pour considérer non pas une succession de triplets indépendants mais plutôt une succession de graphes en étoiles, préservant ainsi les liens entre les triplets. En utilisant cette approche, nous avons amélioré significativement la qualité des réponses de quelques algorithmes d’échantillonnage bien connus dans la littérature pour le délestage des flux. L’analyse de la requête continue permet d’optimiser cette solution en repèrant les données non pertinentes pour être délestées les premières. Dans la deuxième contribution, nous proposons un algorithme de détection de motifs fréquents de graphes RDF dans les flux de données RDF, appelé FreGraPaD (Frequent RDF Graph Patterns Detection). C’est un algorithme en une passe, orienté mémoire et peu coûteux. Il utilise deux structures de données principales un vecteur de bits pour construire et identifier le motif de graphe RDF assurant une optimisation de l’espace mémoire et une table de hachage pour le stockage de ces derniers. La troisième contribution de notre thèse consiste en une solution déterministe de réduction de charge des systèmes RSP appelée POL (Pattern Oriented Load-shedding for RDF Stream Processing systems). Elle utilise des opérateurs booléens très peu coûteux, qu’elle applique aux deux motifs binaires construits de la donnée et de la requête continue pour déterminer et éjecter celle qui est non-pertinente. Elle garantit un rappel de 100%, réduit la charge du système et améliore son temps de réponse. Enfin, notre quatrième contribution est un outil de compression en ligne de flux RDF, appelé Patorc (Pattern Oriented Compression for RSP systems). Il se base sur les motifs fréquents présents dans les flux qu’il factorise. C’est une solution de compression sans perte de données dont l’interrogation sans décompression est très envisageable. Les solutions apportées par cette thèse permettent l’extension des systèmes RSP existants en leur permettant le passage à l’échelle dans un contexte de Bigdata. Elles leur permettent ainsi de manipuler un ou plusieurs flux arrivant à différentes vitesses, sans perdre de leur qualité de réponse et tout en garantissant leur disponibilité au-delà même de leurs limites physiques. Les résultats des expérimentations menées montrent que l’extension des systèmes existants par nos solutions améliore leurs performances. Elles illustrent la diminution considérable de leur temps de réponse, l’augmentation de leur seuil de débit de traitement en entrée tout en optimisant l’utilisation de leurs ressources systèmes / Internet is an infinite source of data coming from sources such as social networks or sensors (home automation, smart city, autonomous vehicle, etc.). These heterogeneous and increasingly large data can be managed through semantic web technologies, which propose to homogenize, link these data and reason above them, and data flow management systems, which mainly address the problems related to volume, volatility and continuous querying. The alliance of these two disciplines has seen the growth of semantic data stream management systems also called RSP (RDF Stream Processing Systems). The objective of this thesis is to allow these systems, via new approaches and "low cost" algorithms, to remain operational, even more efficient, even for large input data volumes and/or with limited system resources.To reach this goal, our thesis is mainly focused on the issue of "Processing semantic data streamsin a context of computer systems with limited resources". It directly contributes to answer the following research questions : (i) How to represent semantic data stream ? And (ii) How to deal with input semantic data when their rates and/or volumes exceed the capabilities of the target system ?As first contribution, we propose an analysis of the data in the semantic data streams in order to consider a succession of star graphs instead of just a success of andependent triples, thus preserving the links between the triples. By using this approach, we significantly impoved the quality of responses of some well known sampling algoithms for load-shedding. The analysis of the continuous query allows the optimisation of this solution by selection the irrelevant data to be load-shedded first. In the second contribution, we propose an algorithm for detecting frequent RDF graph patterns in semantic data streams.We called it FreGraPaD for Frequent RDF Graph Patterns Detection. It is a one pass algorithm, memory oriented and "low-cost". It uses two main data structures : A bit-vector to build and identify the RDF graph pattern, providing thus memory space optimization ; and a hash-table for storing the patterns.The third contribution of our thesis consists of a deterministic load-shedding solution for RSP systems, called POL (Pattern Oriented Load-shedding for RDF Stream Processing systems). It uses very low-cost boolean operators, that we apply on the built binary patterns of the data and the continuous query inorder to determine which data is not relevant to be ejected upstream of the system. It guarantees a recall of 100%, reduces the system load and improves response time. Finally, in the fourth contribution, we propose Patorc (Pattern Oriented Compression for RSP systems). Patorc is an online compression toolfor RDF streams. It is based on the frequent patterns present in RDF data streams that factorizes. It is a data lossless compression solution whith very possible querying without any need to decompression.This thesis provides solutions that allow the extension of existing RSP systems and makes them able to scale in a bigdata context. Thus, these solutions allow the RSP systems to deal with one or more semantic data streams arriving at different speeds, without loosing their response quality while ensuring their availability, even beyond their physical limitations. The conducted experiments, supported by the obtained results show that the extension of existing systems with the new solutions improves their performance. They illustrate the considerable decrease in their engine’s response time, increasing their processing rate threshold while optimizing the use of their system resources

Les capteurs multi- et hyper-spectraux génèrent un énorme flot de données. Un moyen de contourner cette difficulté est de pratiquer une acquisition compressée de l'objet multi- et hyper-spectral. Les données sont alors directement compressées et l'objet est reconstruit lorsqu'on en a besoin. L'étape suivante consiste à éviter cette reconstruction et à travailler directement avec les données compressées pour réaliser un traitement classique sur un objet de cette nature. Après avoir introduit une première approche qui utilise des outils riemanniens pour effectuer une détection de contours dans une image multispectrale, nous présentons les principes de l'acquisition compressée et différents algorithmes utilisés pour résoudre les problèmes qu'elle pose. Ensuite, nous consacrons un chapitre entier à l'étude détaillée de l'un d'entre eux, les algorithmes de type Bregman qui, par leur flexibilité et leur efficacité vont nous permettre de résoudre les minimisations rencontrées plus tard. On s'intéresse ensuite à la détection de signatures dans une image multispectrale et plus particulièrement à un algorithme original du Guo et Osher reposant sur une minimisation $L_1$. Cet algorithme est généralisé dans le cadre de l'acquisition compressée. Une seconde généralisation va permettre de réaliser de la détection de motifs dans une image multispectrale. Et enfin, nous introduirons de nouvelles matrices de mesures qui simplifie énormément les calculs tout en gardant de bonnes qualités de mesures.

Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphes. / For past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters.