Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques. Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTD. / The evolution of web technologies and social trends fostered a shift from traditional enterprise databases to web services and online data. While making data more readily available to users, this evolution also raises additional security concerns regarding the privacy of users and more generally the disclosure of sensitive information. The implementation of appropriate access control models is one of the approaches to mitigate the threat. We investigate an access control model based on (non-materialized) XML views, as presented among others by Fan et al. The simplicity of such views, and in particular the absence of arithmetic features and restructuring, facilitates their modelization with tree alignments. Our objective is therefore to investigate how to manipulate efficiently such views, using formal methods, and especially query rewriting and tree automata. Our research follows essentially three directions: we first develop new algorithms to assess the expressivity of views, in terms of determinacy, query rewriting and certain answers. We show that those problems, although undecidable in our most general setting, can be decided under reasonable restrictions. Then we address the problem of handling updates in the security view framework. And last, we investigate the classical issues raised by schemata, focusing on the specific "determinism'' requirements of DTDs and XML Schemata. In particular, we survey some techniques to approximate the set of all possible view documents with a DTD, and we provide new algorithms to check if the content models of a DTD are deterministic.

Les Smart Grids visent à transformer le réseau électrique actuel en un réseau "plus intelligent" où la production énergétique est décentralisée et automatisée, facilitant l'intégration des sources d'énergie renouvelables. Cette évolution est rendue possible grâce à l'utilisation d'un réseau de communication pour les multiples échanges de données hétérogènes des Smart Grids. L'objectif de cette thèse est de proposer un paradigme de communication efficace en termes de qualité de service pour les Smart Grids basé sur les réseaux de capteurs.Dans un premier temps, on s’intéresse au protocole standard RPL. Nous proposons une évolution de celui-ci à travers une nouvelle fonction objectif. Celle-ci tire parti de l’hétérogénéité matérielle des nœuds et des liens pour introduire la qualité de service. Cela permet à RPL de satisfaire les multiples et différentes exigences en termes de fiabilité, de latence et de priorité dans l'acheminement des données. Nos résultats montrent que notre approche permet bien la différentiation du trafic tout en réduisant la latence du routage et en économisant l'énergie.Nous proposons également d'améliorer l'utilisation du réseau de capteurs en y introduisant l’auto-organisation et la réduction des données. Le but est alors de prédire la valeur des données mesurées plutôt que de les transmettre.Une autre approche explorée est d'agréger les différents messages transitant sur le réseau tout en considérant leurs différentes exigences de qualité de service. Ces deux approches permettent ainsi de réduire la consommation d'énergie tout en respectant les exigences des différentes applications des Smart Grids. / Smart Grids aim to transform the current electric grid into a "smarter" network where energy production is decentralized and automated, which facilitates the integration of renewable energy resources. This evolution is made possible thanks to the use of a communication network for the multiple heterogeneous data exchanges of the Smart Grids. Hence, the aim of this thesis is to propose an efficient communication paradigm in terms of quality of service for Smart Grids based on wireless sensor networks.First, we study data routing in Smart Grids with the RPL standard. Nevertheless, RPL is not suitable for Smart Grid applications in terms of quality of service. Therefore, we propose an objective function for RPL that takes different features of both nodes and links into consideration. Results show that our approach improves network performance compared to existing solutions in terms of packet delivery ratio, network lifetime, latency and traffic differentiation.Then, we also propose a more efficient data collection by introducing self-organization and data reduction for these wireless sensors. The goal is to predict the value of the measured data rather than transmitting them. Another explored approach is to aggregate the different messages sent across the network while considering their different requirements in terms of quality of service.These two approaches reduce the energy consumption while respecting the requirements of the different applications of the Smart Grids.

Les données hospitalières présentent de nombreuses spécificités qui rendent difficilement applicables les méthodes de fouille de données traditionnelles. Dans cette thèse, nous nous intéressons à l'hétérogénéité de ces données ainsi qu'à leur aspect temporel. Dans le cadre du projet ANR ClinMine et d'une convention CIFRE avec la société Alicante, nous proposons deux nouvelles méthodes d'extraction de connaissances adaptées à ces types de données. Dans la première partie, nous développons l'algorithme MOSC (Multi-Objective Sequence Classification) pour la classification supervisée sur données hétérogènes, numériques et temporelles. Cette méthode accepte, en plus des termes binaires ou symboliques, des termes numériques et des séquences d'événements temporels pour former des ensembles de règles de classification. MOSC est le premier algorithme de classification supportant simultanément ces types de données. Dans la seconde partie, nous proposons une méthode de biclustering pour données hétérogènes, un problème qui n'a à notre connaissance jamais été exploré. Cette méthode, HBC (Heterogeneous BiClustering), est étendue pour supporter les données temporelles de différents types : événements temporels et séries temporelles irrégulières. HBC est utilisée pour un cas d'étude sur un ensemble de données hospitalières, dont l'objectif est d'identifier des groupes de patients ayant des profils similaires. Les résultats obtenus sont cohérents et intéressants d'un point de vue médical ; et amènent à la définition de cas d'étude plus précis. L'intégration dans une solution logicielle est également engagée, avec une version parallèle de HBC et un outil de visualisation des résultats. / Hospital data exhibit numerous specificities that make the traditional data mining tools hard to apply. In this thesis, we focus on the heterogeneity associated with hospital data and on their temporal aspect. This work is done within the frame of the ANR ClinMine research project and a CIFRE partnership with the Alicante company. In this thesis, we propose two new knowledge discovery methods suited for hospital data, each able to perform a variety of tasks: classification, prediction, discovering patients profiles, etc.In the first part, we introduce MOSC (Multi-Objective Sequence Classification), an algorithm for supervised classification on heterogeneous, numeric and temporal data. In addition to binary and symbolic terms, this method uses numeric terms and sequences of temporal events to form sets of classification rules. MOSC is the first classification algorithm able to handle these types of data simultaneously. In the second part, we introduce HBC (Heterogeneous BiClustering), a biclustering algorithm for heterogeneous data, a problem that has never been studied so far. This algorithm is extended to support temporal data of various types: temporal events and unevenly-sampled time series. HBC is used for a case study on a set of hospital data, whose goal is to identify groups of patients sharing a similar profile. The results make sense from a medical viewpoint; they indicate that relevant, and sometimes new knowledge is extracted from the data. These results also lead to further, more precise case studies. The integration of HBC within a software is also engaged, with the implementation of a parallel version and a visualization tool for biclustering results.

Depuis quelques années, la recherche sur la normalisation des ensembles de données terminologiques a été une des plus grandes préoccupations d'un groupe de travail du World Wide Web Consortium. Ce travail de recherche a permis de développer un nouveau standard SKOS qui a été ensuite émis en 2009 en tant que recommandation du W3C. Le travail de recherche que nous entreprenons dans ce mémoire concerne ce standard. Notre étude consiste à réaliser à partir de cette recommandation un modèle conceptuel fiable et cohérent reprenant les principaux éléments de SKOS et de son extension. Elle consiste aussi à prototyper un outil reposant sur ce modèle qui permettrait de gérer, de manipuler et de partager des ensembles de données terminologiques basés sur SKOS. Pour ce faire, une méthodologie de recherche bien précise a été adoptée et diverses recherches concernant le standard SKOS et le type d'ensemble de données terminologiques ont été réalisées. A partir de ces recherches, nous avons proposé un modèle conceptuel de SKOS et nous avons conçu et prototypé l'outil le supportant, qui a été par la suite testé à travers des cas d'utilisation réels. Ces tests ont permis d'évaluer l'outil et de démontrer sa capacité à manipuler des données normalisées en SKOS en toute simplicité. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Gestion de connaissances, SKOS, RDF, gestion des KOS, ensembles de données terminologiques basés sur SKOS, exportation SKOS, glossaires, thésaurus.

Le forage de données, appelé également "Découverte de connaissance dans les bases de données" , est un jeune domaine de recherche interdisciplinaire. Le forage de données étudie les processus d'analyse de grands ensembles de données pour en extraire des connaissances, et les processus de transformation de ces connaissances en des structures faciles à comprendre et à utiliser par les humains. Cette thèse étudie deux tâches importantes dans le domaine du forage de données : la détection des anomalies et la recommandation de produits. La détection des anomalies est l'identification des données non conformes aux observations normales. La recommandation de produit est la prédiction du niveau d'intérêt d'un client pour des produits en se basant sur des données d'achats antérieurs et des données socio-économiques. Plus précisément, cette thèse porte sur 1) la détection des anomalies dans de grands ensembles de données de type catégorielles; et 2) les techniques de recommandation à partir des données de classements asymétriques. La détection des anomalies dans des données catégorielles de grande échelle est un problème important qui est loin d'être résolu. Les méthodes existantes dans ce domaine souffrnt d'une faible efficience et efficacité en raison de la dimensionnalité élevée des données, de la grande taille des bases de données, de la complexité élevée des tests statistiques, ainsi que des mesures de proximité non adéquates. Cette thèse propose une définition formelle d'anomalie dans les données catégorielles ainsi que deux algorithmes efficaces et efficients pour la détection des anomalies dans les données de grande taille. Ces algorithmes ont besoin d'un seul paramètre : le nombre des anomalies. Pour déterminer la valeur de ce paramètre, nous avons développé un critère en nous basant sur un nouveau concept qui est l'holo-entropie. Plusieurs recherches antérieures sur les systèmes de recommandation ont négligé un type de classements répandu dans les applications Web, telles que le commerce électronique (ex. Amazon, Taobao) et les sites fournisseurs de contenu (ex. YouTube). Les données de classements recueillies par ces sites se différencient de celles de classements des films et des musiques par leur distribution asymétrique élevée. Cette thèse propose un cadre mieux adapté pour estimer les classements et les préférences quantitatives d'ordre supérieur pour des données de classements asymétriques. Ce cadre permet de créer de nouveaux modèles de recommandation en se basant sur la factorisation de matrice ou sur l'estimation de voisinage. Des résultats expérimentaux sur des ensembles de données asymétriques indiquent que les modèles créés avec ce cadre ont une meilleure performance que les modèles conventionnels non seulement pour la prédiction de classements, mais aussi pour la prédiction de la liste des Top-N produits.

Titre de l'écran-titre (visionné le 7 février 2024) / La croissance rapide des données dans différentes applications telles que la communication en temps réel, les systèmes automobiles et la visioconférence a souligné la nécessité de techniques efficaces de compression des données. La compression des données réduit les besoins de stockage et de transmission des données. La codification d'entropie, qui est une compression de données sans perte, est une méthode largement utilisée. La codification d'entropie consiste à coder des symboles d'une séquence d'entrée en utilisant moins de bits pour les représenter, ce qui réduit la taille totale des données. La codification de Huffman, qui est une technique rapide de codage d'entropie, est utilisée pour sa vitesse et son accélération matérielle. Cependant, son taux de compression n'est pas toujours optimal. Cela devient évident lorsqu'il s'agit de petits alphabets et de symboles avec des probabilités d'occurrence élevées. La codification arithmétique, une méthode alternative, offre de meilleurs taux de compression, mais elle a une complexité computationnelle élevée. Les systèmes de numération asymétriques (ANS), qui sont une approche de codage d'entropie, visent à approcher la limite théorique de la compression des données tout en maintenant une complexité computationnelle inférieure par rapport à la codification arithmétique. ANS comprend deux versions principales : ANS à plage et ANS tabulé. Ce dernier, appelé tANS, utilise une table pour les procédures de codage et de décodage, ce qui le rend plus adapté à une implémentation matérielle. Cependant, bien qu'ANS présente des avantages, des défis subsistent. Trouver une table de codage appropriée, ou un segment clé, pour tANS est important pour son efficacité. Des recherches récentes explorent différentes techniques pour concevoir des segments clés optimaux, en tenant compte de facteurs tels que les probabilités des symboles, l'alphabet source et la taille de la table souhaitée. Le défi consiste à construire un segment clé qui satisfait aux conditions de codage et qui conduit à une longueur moyenne minimale des codes. La technique de tri d'états proposée par Yokoo et Dubé vise à optimiser les segments clés en triant les états en fonction de leurs probabilités stationnaires. Cependant, cette méthode est sous-optimale dans certains cas. L'objectif de cette recherche est d'étudier les limitations et la sous-optimalité de l'algorithme de tri des états en présentant un exemple dans lequel la stratégie de Yokoo et Dubé ne créera pas le segment optimal. Cela permettra une meilleure compréhension des complexités de la conception de clés tANS optimales. Cette étude contribue à l'avancement des techniques de compression des données en abordant les défis et les améliorations possibles dans le contexte du codage d'entropie, en particulier dans le cadre d'ANS et de ses variantes. Cette recherche vise à améliorer notre compréhension de la conception de clés pour tANS et à ouvrir la voie à des solutions plus efficaces pour la compression et la transmission des données dans le paysage numérique en constante évolution. / In the modern world, the significant increase of data has resulted in the demand for efficient data handling in terms of transfer and storage. As hardware advances, data compression has become an essential research field to address this challenge. Rooted in the fusion of mathematics and computer science, data compression utilizes algorithms to reduce data size and optimize storage capacity. This process involves both compression and reconstruction algorithms, seeking to keep similarity of the original data and the reconstructed data. By compression data, the speed of data transfer increases significantly, while the costs of storage hardware and network bandwidth decrease. Data compression divides into two categories: lossy and lossless compression. In lossy compression we may have some loss of information during reconstruction. Contrarily, lossless compression, in which input and output remain equal, is suited for systems involving sensitive data or databases. This thesis focuses on addressing weaknesses of the tANS method, with a particular emphasis on investigating the sub-optimality of the state-sorting technique presented by Yokoo and Dubé. The study discusses the limitations of this technique and explains ANS methods, particularly the theoretical analysis of tANS. The research illustrates an example emphasizing sub-optimality in the state-sorting technique. In conclusion, this research offers valuable insights into the challenges and potential enhancements of tANS compression technique. By delving deeper into the intricacies of ANS-based methods, researchers can contribute to the development of more efficient compression strategies, providing better data handling in an increasingly digitized world.

Les données massives se situent au coeur de beaucoup d’enjeux scientifiques et sociétaux, et leur volume global ne cesse de croître. Il devient donc crucial de disposer de solutions permettant leur traitement et leur analyse. Hélas, alors qu’une majorité de ces données intègrent une composante spatiale vectorielle, peu de systèmes sont à même de gérer cette dernière. En outre, les rares prototypes qui s’y essaient respectent mal les standards ISO et les spécifications OGC et présentent des performances limitées. La présente recherche visait donc à déterminer comment gérer les données spatiales massives vectorielles de façon plus complète et efficiente. Il s’agissait en particulier de trouver une façon de les indexer avec une bonne scalabilité horizontale, d’assurer leur compatibilité avec la norme ISO-19125 et ses extensions, et de les rendre accessibles depuis les logiciels SIG. Il en résulte le système Elcano, une extension spatiale au système de gestion de données massives Spark qui fournit des performances accrues par rapport aux solutions du marché. / Big data are in the midst of many scientific and economic issues. Furthermore their volume is continuously increasing. As a result, the need for management and processing solutions has become critical. Unfortunately, while most of these data have a vectorial spatial component, almost none of the current systems are able to manage it. In addition, the few systems who try either do not respect the ISO standards and OGC specifications or show poor performances. The aim of this research was then to determine how to manage the vectorial massive data more completely and efficiently. The objective was to find a scalable way of indexing them, ensuring their compatibility with ISO-19125 and its extensions, and making them accessible from GIS. The result is the Elcano system. It is an extension of the massive data management system Spark which provides increased performance compared to current market solutions.

Au cours des dernières années, nous avons constaté une augmentation du volume d’information sous la forme de flux de données. Cette augmentation rend le traitement de ces flux par des méthodes traditionnelles non performant, voire impossible. De plus, la mise à jour rapide des informations suscite un intérêt grandissant pour leurs traitements en temps réel afin d’en tirer une plus grande valeur. Ces données massives étant souvent géoréférencées, il devient donc pertinent d’offrir des méthodes permettant d’effectuer des traitements spatiaux sur ces flux massifs de données. Cependant, le sujet des traitements spatiaux dans un contexte de flux massifs a très peu été abordé dans la recherche scientifique. Les études qui ont été faites traitaient toujours de flux massif de données en relation avec des données persistantes. Aucune recherche ne portait sur des traitements spatiaux ayant plusieurs flux massifs de données spatiales. La problématique est de déterminer des méthodes de traitements pour des opérateurs spatiaux dont les paramètres sont issus de flux massifs de données spatiales. Notre objectif général consiste à explorer les caractéristiques permettant l’élaboration de tels traitements et d’offrir des pistes de solution. Nos travaux de recherche ont fait ressortir les facteurs influençant l’adaptation des traitements spatiaux dans un contexte de traitement en parallèle de flux massif de données. Nous avons déterminé que les méthodes d’adaptation peuvent se décliner en classes sur la base des caractéristiques de l’opérateur spatial, mais aussi sur la nature des données et la façon dont elles sont rendues disponibles. Nous avons proposé des méthodes générales de traitement pour chacune des classes identifiées afin de guider les stratégies d’adaptations. Pour la classe dont le traitement d’opérateur binaire possède des opérandes issus de flux massifs, nous avons détaillé une méthode d’adaptation permettant l’utilisation d’opérateurs spatiaux. Afin de tester l’efficacité et la validité de la méthode proposée, nous avons appliqué cette méthode à un opérateur relationnel d’intersection et un opérateur d’analyse de proximité, soit les "k" plus proches voisins. Ces tests ont permis de vérifier la validité et de quantifier l’efficacité des méthodes proposée par rapport à l’évolution, ou scalabilité, horizontale du système (ajout du nombre de cœurs). Nos tests ont aussi permis de quantifier l’effet de la variation du niveau de partitionnement sur les performances du débit de traitement. Notre contribution permettra, nous l’espérons, de servir de point de départ pour l’adaptation d’opérateurs spatiaux plus complexes. / In recent years we have witnessed a significant volume increase of data streams. The traditional way of processing this information is rendered inefficient or even impossible by this high volume of data. There is an increase in the interest of real time data processing in order to derive greater value of the data. Since those data are often georeferenced, it becomes relevant to offer methods that enable spatial processing on big data streams. However, the subject of spatial processing in a context of Big Data stream has seldom been discussed in scientific research. All the studies that have been done so far involve persistent data and none of them deals with the case where two Big Data streams are in relation. The problem is therefore to determine how to adapt the processing of spatial operators when their parameters derive from two Big Spatial Data stream. Our general objective is to explore the characteristics that allow the development of such analysis and to offer potential solutions. Our research has highlighted the factors influencing the adaptation of spatial processing in a context of Big Data stream. We have determined that adaptation methods can be categorized in different categories according to the characteristics of the spatial operator but also on the characteristics of the data itself and how it is made available. We proposed general methods of spatial processing for each category in order to guide adaptation strategies. For one of these categories, where a binary operator has both operands coming from Big Data stream, we have detailed a method allowing the use of spatial operators. In order to test the effectiveness and validity of the proposed method, we applied this method to an intersection operator and to a proximity analysis operator, the "k" nearest neighbors. These tests made it possible to check the validity and to quantify the effectiveness of the proposed methods in relation to the system evolution or scalability, i.e. increasing the number of processing cores. Our tests also made it possible to quantify the effect of the variation of the partitioning level on the performances of the treatment flow. Our contribution will, hopefully, serves as a starting point for more complex spatial operator adaptation.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.