Dissertations / Theses: 'Graphe massifs'

1

Nabti, Chems Eddine. "Subgraph Isomorphism Search In Massive Graph Data." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1293/document.

Full text

Abstract:

L'interrogation de graphes de données est un problème fondamental qui connait un grand intérêt, en particulier pour les données structurées massives où les graphes constituent une alternative prometteuse aux bases de données relationnelles pour la modélisation des grandes masses de données. Cependant, l'interrogation des graphes de données est différente et plus complexe que l'interrogation des données relationnelles à base de tables. La tâche principale impliquée dans l'interrogation de graphes de données est la recherche d'isomorphisme de sous-graphes qui est un problème NP-complet.La recherche d'isomorphisme de sous-graphes est un problème très important impliqué dans divers domaines comme la reconnaissance de formes, l'analyse des réseaux sociaux, la biologie, etc. Il consiste à énumérer les sous-graphes d'un graphe de données qui correspondent à un graphe requête. Les solutions les plus connues de ce problème sont basées sur le retour arrière (backtracking). Elles explorent un grand espace de recherche, ce qui entraîne un coût de traitement élevé, notamment dans le cas de données massives.Pour réduire le temps et la complexité en espace mémoire dans la recherche d'isomorphisme de sous-graphes, nous proposons d'utiliser des graphes compressés. Dans notre approche, la recherche d'isomorphisme de sous-graphes est réalisée sur une représentation compressée des graphes sans les décompresser. La compression des graphes s'effectue en regroupant les sommets en super-sommets. Ce concept est connu dans la théorie des graphes par la décomposition modulaire. Il sert à générer une représentation en arbre d'un graphe qui met en évidence des groupes de sommets qui ont les mêmes voisins. Avec cette compression, nous obtenons une réduction substantielle de l'espace de recherche et par conséquent, une économie significative dans le temps de traitement.Nous proposons également une nouvelle représentation des sommets du graphe, qui simplifie le filtrage de l'espace de recherche. Ce nouveau mécanisme appelé compact neighborhood Index (CNI) encode l'information de voisinage autour d'un sommet en un seul entier. Cet encodage du voisinage réduit la complexité du temps de filtrage de cubique à quadratique. Ce qui est considérable pour les données massifs.Nous proposons également un algorithme de filtrage itératif qui repose sur les caractéristiques des CNIs pour assurer un élagage global de l'espace de recherche.Nous avons évalué nos approches sur plusieurs datasets et nous les avons comparées avec les algorithmes de l’état de l’art
Querying graph data is a fundamental problem that witnesses an increasing interest especially for massive structured data where graphs come as a promising alternative to relational databases for big data modeling. However, querying graph data is different and more complex than querying relational table-based data. The main task involved in querying graph data is subgraph isomorphism search which is an NP-complete problem. Subgraph isomorphism search, is an important problem which is involved in various domains such as pattern recognition, social network analysis, biology, etc. It consists to enumerate the subgraphs of a data graph that match a query graph. The most known solutions of this problem are backtracking-based. They explore a large search space which results in a high computational cost when we deal with massive graph data. To reduce time and memory space complexity of subgraph isomorphism search. We propose to use compressed graphs. In our approach, subgraph isomorphism search is achieved on compressed representations of graphs without decompressing them. Graph compression is performed by grouping vertices into super vertices. This concept is known, in graph theory, as modular decomposition. It is used to generate a tree representation of a graph that highlights groups of vertices that have the same neighbors. With this compression we obtain a substantial reduction of the search space and consequently a significant saving in the processing time. We also propose a novel encoding of vertices that simplifies the filtering of the search space. This new mechanism is called compact neighborhood Index (CNI). A CNI distills all the information around a vertex in a single integer. This simple neighborhood encoding reduces the time complexity of vertex filtering from cubic to quadratic which is considerable for big graphs. We propose also an iterative local global filtering algorithm that relies on the characteristics of CNIs to ensure a global pruning of the search space.We evaluated our approaches on several real-word datasets and compared them with the state of the art algorithms

APA, Harvard, Vancouver, ISO, and other styles

2

Bletterer, Arnaud. "Une approche basée graphes pour la modélisation et le traitement de nuages de points massifs issus d’acquisitions de LiDARs terrestres." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4218/document.

Full text

Abstract:

Avec l'évolution des dispositifs d'acquisition 3D, les nuages de points sont maintenant devenus une représentation essentielle des scènes numérisées. Les systèmes récents sont capables de capturer plusieurs centaines de millions de points en une seule acquisition. Comme plusieurs acquisitions sont nécessaires pour capturer la géométrie de scènes de grande taille, un site historique par exemple, nous obtenons des nuages de points massifs, i.e., composés de plusieurs milliards de points. Dans cette thèse, nous nous intéressons à la structuration et à la manipulation de nuages de points issus d'acquisitions générées à partir de LiDARs terrestres. A partir de la structure de chaque acquisition, des graphes, représentant chacun la connectivité locale de la surface numérisée, sont construits. Les graphes créés sont ensuite liés entre eux afin d'obtenir une représentation globale de la surface capturée. Nous montrons que cette structure est particulièrement adaptée à la manipulation de la surface sous-jacente aux nuages de points massifs, même sur des ordinateurs ayant une mémoire limitée. Notamment, nous montrons que cette structure permet de traiter deux problèmes spécifiques à ce type de données. Un premier lié au ré-échantillonnage de nuages de points, en générant des distributions de bonne qualité en termes de bruit bleu grâce à un algorithme d'échantillonnage en disques de Poisson. Un autre lié à la construction de diagrammes de Voronoï centroïdaux, permettant l'amélioration de la qualité des distributions générées, ainsi que la reconstruction de maillages triangulaires
With the evolution of 3D acquisition devices, point clouds have now become an essential representation of digitized scenes. Recent systems are able to capture several hundreds of millions of points in a single acquisition. As multiple acquisitions are necessary to capture the geometry of large-scale scenes, a historical site for example, we obtain massive point clouds, i.e., composed of billions of points. In this thesis, we are interested in the structuration and manipulation of point clouds from acquisitions generated by terrestrial LiDARs. From the structure of each acquisition, graphs, each representing the local connectivity of the digitized surface, are constructed. Created graphs are then linked together to obtain a global representation of the captured surface. We show that this structure is particularly adapted to the manipulation of the underlying surface of massive point clouds, even on computers with limited memory. Especially, we show that this structure allow to deal with two problems specific to that kind of data. A first one linked to the resampling of point clouds, by generating distributions of good quality in terms of blue noise thanks to a Poisson disk sampling algorithm. Another one connected to the construction of centroidal Voronoi tessellations, allowing to enhance the quality of generated distributions and to reconstruct triangular meshes

APA, Harvard, Vancouver, ISO, and other styles

3

Baudin, Alexis. "Cliques statiques et temporelles : algorithmes d'énumération et de détection de communautés." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS609.

Full text

Abstract:

Les graphes sont des objets mathématiques qui permettent de modéliser des interactions ou connexions entre entités de types variés. Un graphe peut représenter par exemple un réseau social qui connecte les utilisateurs entre eux, un réseau de transport comme le métro où les stations sont connectées entre elles, ou encore un cerveau avec les milliards de neurones en interaction qu'il contient. Depuis quelques années, la forte dynamicité de ces structures a été mise en évidence, ainsi que l'importance de prendre en compte l'évolution temporelle de ces réseaux pour en comprendre le fonctionnement. Alors que de nombreux concepts et algorithmes ont été développés sur les graphes pour décrire des structures de réseaux statiques, il reste encore beaucoup à faire pour formaliser et développer des algorithmes pertinents pour décrire la dynamique des réseaux réels. Cette thèse vise à mieux comprendre comment sont structurés les graphes massifs qui sont issus du monde réel et à développer des outils pour étendre notre compréhension à des structures évoluant dans le temps. Il a été montré que ces graphes ont des propriétés particulières, qui les distinguent des graphes théoriques ou tirés aléatoirement. Exploiter ces propriétés permet alors de concevoir des algorithmes pour résoudre certains problèmes difficiles beaucoup plus rapidement sur ces instances que dans le cas général. La thèse se focalise sur les cliques, qui sont des groupes d'éléments tous connectés entre eux. Nous étudions l'énumération des cliques dans les graphes statiques et temporels et la détection de communautés qu'elles permettent de mettre en œuvre. Les communautés d'un graphe sont des ensembles de sommets tels qu'au sein d'une communauté, les sommets interagissent fortement entre eux, et peu avec le reste du graphe. Leur étude aide à comprendre les propriétés structurelles et fonctionnelles des réseaux. Nous évaluons nos algorithmes sur des graphes massifs issus du monde réel, ouvrant ainsi de nouvelles perspectives pour comprendre les interactions au sein de ces réseaux. Nous travaillons d'abord sur des graphes, sans tenir compte de la composante temporelle des interactions. Nous commençons par utiliser la méthode de détection de communautés par percolation de cliques, en mettant en évidence ses limites en mémoire, qui empêchent de l'appliquer à des graphes trop massifs. En introduisant un algorithme de résolution approchée du problème, nous dépassons cette limite. Puis, nous améliorons l'énumération des cliques maximales dans le cas des graphes particuliers dits bipartis. Ils correspondent à des interactions entre des groupes de sommets de type différent, par exemple des liens entre des personnes et du contenu consulté, la participation à des événements, etc. Ensuite, nous considérons des interactions qui ont lieu au cours du temps, grâce au formalisme des flots de liens. Nous cherchons à étendre les algorithmes présentés en première partie, pour exploiter leurs avantages dans l'étude des interactions temporelles. Nous fournissons un nouvel algorithme d'énumération des cliques maximales dans les flots de liens, beaucoup plus efficace que l'état de l'art sur des jeux de données massifs. Enfin, nous nous intéressons aux communautés dans les flots de liens par percolation de cliques, en développant une extension de la méthode utilisée sur les graphes. Les résultats montrent une amélioration significative par rapport à l'état de l'art, et nous analysons les communautés obtenues pour fournir des informations pertinentes sur l'organisation des interactions temporelles dans les flots de liens. Mon travail de thèse a permis d’apporter de nouvelles réflexions sur l’étude des réseaux massifs issus du monde réel. Cela montre l'importance d'explorer le potentiel des graphes dans un contexte réel, et pourrait contribuer à l'émergence de solutions novatrices pour les défis complexes de notre société moderne
Graphs are mathematical objects used to model interactions or connections between entities of various types. A graph can represent, for example, a social network that connects users to each other, a transport network like the metro where stations are connected to each other, or a brain with the billions of interacting neurons it contains. In recent years, the dynamic nature of these structures has been highlighted, as well as the importance of taking into account the temporal evolution of these networks to understand their functioning. While many concepts and algorithms have been developed on graphs to describe static network structures, much remains to be done to formalize and develop relevant algorithms to describe the dynamics of real networks. This thesis aims to better understand how massive graphs are structured in the real world, and to develop tools to extend our understanding to structures that evolve over time. It has been shown that these graphs have particular properties, which distinguish them from theoretical or randomly drawn graphs. Exploiting these properties then enables the design of algorithms to solve certain difficult problems much more quickly on these instances than in the general case. My PhD thesis focuses on cliques, which are groups of elements that are all connected to each other. We study the enumeration of cliques in static and temporal graphs and the detection of communities they enable. The communities of a graph are sets of vertices such that, within a community, the vertices interact strongly with each other, and little with the rest of the graph. Their study helps to understand the structural and functional properties of networks. We are evaluating our algorithms on massive real-world graphs, opening up new perspectives for understanding interactions within these networks. We first work on graphs, without taking into account the temporal component of interactions. We begin by using the clique percolation method of community detection, highlighting its limitations in memory, which prevent it from being applied to graphs that are too massive. By introducing an approximate problem-solving algorithm, we overcome this limitation. Next, we improve the enumeration of maximal cliques in the case of bipartite graphs. These correspond to interactions between groups of vertices of different types, e.g. links between people and viewed content, participation in events, etc. Next, we consider interactions that take place over time, using the link stream formalism. We seek to extend the algorithms presented in the first part, to exploit their advantages in the study of temporal interactions. We provide a new algorithm for enumerating maximal cliques in link streams, which is much more efficient than the state-of-the-art on massive datasets. Finally, we focus on communities in link streams by clique percolation, developing an extension of the method used on graphs. The results show a significant improvement over the state of the art, and we analyze the communities obtained to provide relevant information on the organization of temporal interactions in link streams. My PhD work has provided new insights into the study of massive real-world networks. This shows the importance of exploring the potential of graphs in a real-world context, and could contribute to the emergence of innovative solutions for the complex challenges of our modern society

APA, Harvard, Vancouver, ISO, and other styles

4

Hinge, Antoine. "Dessin de graphe distribué par modèle de force : application au Big Data." Thesis, Bordeaux, 2018. http://www.theses.fr/2018BORD0092/document.

Full text

Abstract:

Les graphes, outil mathématique pour modéliser les relations entre des entités, sont en augmentation constante du fait d'internet (par exemple les réseaux sociaux). La visualisation de graphe (aussi appelée dessin) permet d'obtenir immédiatement des informations sur le graphe. Les graphes issus d'internet sont généralement stockés de manière morcelée sur plusieurs machines connectées par un réseau. Cette thèse a pour but de développer des algorithmes de dessin de très grand graphes dans le paradigme MapReduce, utilisé pour le calcul sur cluster. Parmi les algorithmes de dessin, les algorithmes reposants sur un modèle physique sous-jacent pour réaliser le dessin permettent d'obtenir un bon dessin indépendamment de la nature du graphe. Nous proposons deux algorithmes par modèle de forces conçus dans le paradigme MapReduce. GDAD, le premier algorithme par modèle de force dans le paradigme MapReduce, utilise des pivots pour simplifier le calcul des interactions entre les nœuds du graphes. MuGDAD, le prolongement de GDAD, utilise une simplification récursive du graphe pour effectuer le dessin, toujours à l'aide de pivots. Nous comparons ces deux algorithmes avec les algorithmes de l'état de l'art pour évaluer leurs performances
Graphs, usually used to model relations between entities, are continually growing mainly because of the internet (social networks for example). Graph visualization (also called drawing) is a fast way of collecting data about a graph. Internet graphs are often stored in a distributed manner, split between several machines interconnected. This thesis aims to develop drawing algorithms to draw very large graphs using the MapReduce paradigm, used for cluster computing. Among graph drawing algorithms, those which rely on a physical model to compute the node placement are generally considered to draw graphs well regardless of the type of graph. We developped two force-directed graph drawing algorithms in the MapReduce paradigm. GDAD, the fist distributed force-directed graph drawing algorithm ever, uses pivots to simplify computations of node interactions. MuGDAD, following GDAD, uses a recursive simplification to draw the original graph, keeping the pivots. We compare these two algorithms with the state of the art to assess their performances

APA, Harvard, Vancouver, ISO, and other styles

5

Hernández, Rivas Cecilia Paola. "Managing massive graphs." Tesis, Universidad de Chile, 2014. http://repositorio.uchile.cl/handle/2250/131839.

Full text

Abstract:

Doctora en Ciencias, Mención Computación
Con la popularidad de la Web y, mas recientemente, el amplio uso de las redes sociales, la necesidad de procesar y encontrar información en grafos muy grandes impone varios desafíos: Cómo procesar grafos muy grandes e cientemente, dado que probablemente son muy grandes para la memoria disponible, o incluso si la memoria es su ciente, realizar un paso sobre el grafo es todavía caro computacionalmente? Cómo almacenar esos grafos e cientemente, para ser archivados, o para ejecutar algoritmos de grafos? Cómo descubrir información relevante tal como componentes densos, comunidades, u otras estructuras? Se han propuesto tres enfoques para manejar grafos grandes. El primero es usar formatos de grafos comprimidos que permiten consultas de navegación básicas directamentee sobre la estructura comprimida, sin la necesidad de descompresión. Esto permite simular cualquier algoritmo de grafo en memoria principal usando mucho menos espacio que la representación plana. Una segunda línea de investigación se focaliza en usar modelos de stream o semi- stream de datos de manera de procesar secuencialmente, idealmente en un paso sobre el disco, usando una cantidad limitada de memoria principal. La tercera línea es el uso de sistemas distribuidos y paralelos donde la memoria es agregada sobre múltiples unidades de procesamiento para procesar el grafo en paralelo. En esta tesis presentamos varios enfoques para manejar grafos grandes (con arcos sin etiquetas) considerando los tres enfoques. Primero, buscamos por patrones que aparecen en grafos de la Web y redes sociales los que podemos representar en forma compacta, en particular mostramos como generalizar algoritmos para encontrar cliques o bicliques para encontrar sub-estructuras densas que comprimen ambas. Segundo, basado en estos subgrafos densos, proponemos esquemas comprimidos que soportan consultas de vecinos directos y reversos, así como otras consultas mas complejas sobre subgrafos densos. Algunas de las contribuciones combinan técnicas del estado del arte mientras otras incluyen representaciones comprimidas novedosas basadas en estructuras de datos compactas. Encontrar subgrafos densos es una tarea que consume tiempo y espacio, así que proporcionamos algoritmos de streaming and algoritmos de memoria externa para descubrir subgrafos densos, asi como también algoritmos distribuidos para construir las estructuras básicas que usamos para las representaciones comprimidas.

APA, Harvard, Vancouver, ISO, and other styles

6

Gillet, Noel. "Optimisation de requêtes sur des données massives dans un environnement distribué." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0553/document.

Full text

Abstract:

Les systèmes de stockage distribués sont massivement utilisés dans le contexte actuel des grandes masses de données. En plus de gérer le stockage de ces données, ces systèmes doivent répondre à une quantité toujours plus importante de requêtes émises par des clients distants afin d’effectuer de la fouille de données ou encore de la visualisation. Une problématique majeure dans ce contexte consiste à répartir efficacement les requêtes entre les différents noeuds qui composent ces systèmes afin de minimiser le temps de traitement des requêtes ( temps maximum et en moyenne d’une requête, temps total de traitement pour toutes les requêtes...). Dans cette thèse nous nous intéressons au problème d’allocation de requêtes dans un environnement distribué. On considère que les données sont répliquées et que les requêtes sont traitées par les noeuds stockant une copie de la donnée concernée. Dans un premier temps, des solutions algorithmiques quasi-optimales sont proposées lorsque les communications entre les différents noeuds du système se font de manière asynchrone. Le cas où certains noeuds du système peuvent être en panne est également considéré. Dans un deuxième temps, nous nous intéressons à l’impact de la réplication des données sur le traitement des requêtes. En particulier, un algorithme qui adapte la réplication des données en fonction de la demande est proposé. Cet algorithme couplé à nos algorithmes d’allocation permet de garantir une répartition des requêtes proche de l’idéal pour toute distribution de requêtes. Enfin, nous nous intéressons à l’impact de la réplication quand les requêtes arrivent en flux sur le système. Nous procédons à une évaluation expérimentale sur la base de données distribuées Apache Cassandra. Les expériences réalisées confirment l’intérêt de la réplication et de nos algorithmes d’allocation vis-à-vis des solutions présentes par défaut dans ce système
Distributed data store are massively used in the actual context of Big Data. In addition to provide data management features, those systems have to deal with an increasing amount of queries sent by distant users in order to process data mining or data visualization operations. One of the main challenge is to evenly distribute the workload of queries between the nodes which compose these system in order to minimize the treatment time. In this thesis, we tackle the problem of query allocation in a distributed environment. We consider that data are replicated and a query can be handle only by a node storing the concerning data. First, near-optimal algorithmic proposals are given when communications between nodes are asynchronous. We also consider that some nodes can be faulty. Second, we study more deeply the impact of data replication on the query treatement. Particularly, we present an algorithm which manage the data replication based on the demand on these data. Combined with our allocation algorithm, we guaranty a near-optimal allocation. Finally, we focus on the impact of data replication when queries are received as a stream by the system. We make an experimental evaluation using the distributed database Apache Cassandra. The experiments confirm the interest of our algorithmic proposals to improve the query treatement compared to the native allocation scheme in Cassandra

APA, Harvard, Vancouver, ISO, and other styles

7

Wang, Guan. "STREAMING HYPERGRAPH PARTITION FOR MASSIVE GRAPHS." Kent State University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=kent1385097649.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Habi, Abdelmalek. "Search and Aggregation in Big Graphs." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1259/document.

Full text

Abstract:

Ces dernières années ont connu un regain d'intérêt pour l'utilisation des graphes comme moyen fiable de représentation et de modélisation des données, et ce, dans divers domaines de l'informatique. En particulier, pour les grandes masses de données, les graphes apparaissent comme une alternative prometteuse aux bases de données relationnelles. Plus particulièrement, le recherche de sous-graphes s'avère être une tâche cruciale pour explorer ces grands jeux de données. Dans cette thèse, nous étudions deux problématiques principales. Dans un premier temps, nous abordons le problème de la détection de motifs dans les grands graphes. Ce problème vise à rechercher les k-meilleures correspondances (top-k) d'un graphe motif dans un graphe de données. Pour cette problématique, nous introduisons un nouveau modèle de détection de motifs de graphe nommé la Simulation Relaxée de Graphe (RGS), qui permet d’identifier des correspondances de graphes avec un certain écart (structurel) et ainsi éviter le problème de réponse vide. Ensuite, nous formalisons et étudions le problème de la recherche des k-meilleures réponses suivant deux critères, la pertinence (la meilleure similarité entre le motif et les réponses) et la diversité (la dissimilarité entre les réponses). Nous considérons également le problème des k-meilleures correspondances diversifiées et nous proposons une fonction de diversification pour équilibrer la pertinence et la diversité. En outre, nous développons des algorithmes efficaces basés sur des stratégies d’optimisation en respectant le modèle proposé. Notre approche est efficiente en terme de temps d’exécution et flexible en terme d'applicabilité. L’analyse de la complexité des algorithmes et les expérimentations menées sur des jeux de données réelles montrent l’efficacité des approches proposées. Dans un second temps, nous abordons le problème de recherche agrégative dans des documents XML. Pour un arbre requête, l'objectif est de trouver des motifs correspondants dans un ou plusieurs documents XML et de les agréger dans un seul agrégat. Dans un premier temps nous présentons la motivation derrière ce paradigme de recherche agrégative et nous expliquons les gains potentiels par rapport aux méthodes classiques de requêtage. Ensuite nous proposons une nouvelle approche qui a pour but de construire, dans la mesure du possible, une réponse cohérente et plus complète en agrégeant plusieurs résultats provenant de plusieurs sources de données. Les expérimentations réalisées sur plusieurs ensembles de données réelles montrent l’efficacité de cette approche en termes de pertinence et de qualité de résultat
Recent years have witnessed a growing renewed interest in the use of graphs as a reliable means for representing and modeling data. Thereby, graphs enable to ensure efficiency in various fields of computer science, especially for massive data where graphs arise as a promising alternative to relational databases for big data modeling. In this regard, querying data graph proves to be a crucial task to explore the knowledge in these datasets. In this dissertation, we investigate two main problems. In the first part we address the problem of detecting patterns in larger graphs, called the top-k graph pattern matching problem. We introduce a new graph pattern matching model named Relaxed Graph Simulation (RGS), to identify significant matches and to avoid the empty-set answer problem. We formalize and study the top-k matching problem based on two classes of functions, relevance and diversity, for ranking the matches according to the RGS model. We also consider the diversified top-k matching problem, and we propose a diversification function to balance relevance and diversity. Moreover, we provide efficient algorithms based on optimization strategies to compute the top-k and the diversified top-k matches according to the proposed model. The proposed approach is optimal in terms of search time and flexible in terms of applicability. The analyze of the time complexity of the proposed algorithms and the extensive experiments on real-life datasets demonstrate both the effectiveness and the efficiency of these approaches. In the second part, we tackle the problem of graph querying using aggregated search paradigm. We consider this problem for particular types of graphs that are trees, and we deal with the query processing in XML documents. Firstly, we give the motivation behind the use of such a paradigm, and we explain the potential benefits compared to traditional querying approaches. Furthermore, we propose a new method for aggregated tree search, based on approximate tree matching algorithm on several tree fragments, that aims to build, the extent possible, a coherent and complete answer by combining several results. The proposed solutions are shown to be efficient in terms of relevance and quality on different real-life datasets

APA, Harvard, Vancouver, ISO, and other styles

9

Jiang, Jiaxin. "Efficient frameworks for keyword search on massive graphs." HKBU Institutional Repository, 2020. https://repository.hkbu.edu.hk/etd_oa/806.

Full text

Abstract:

Due to the unstructuredness and the lack of schema information of knowledge graphs, social networks and RDF graphs, keyword search has been proposed for querying such graphs/networks. Recently, various keyword search semantics have been designed. However, these keyword search semantics and algorithms encounter efficiency or scalability issues. In this thesis, we propose new three generic frameworks or index techniques to address these issues. The thesis results show that the keyword search on massive graphs under different scenarios can be effective and efficient, which would facilitate keyword search services on graphs in the real world. First, we study the keyword search on massive knowledge graphs. In particular, we propose a generic ontology- based indexing framework for keyword search, called Bisimulation of Generalized Graph Index (BiG-index), to enhance the search performance. The novelties of BiG-index reside in using an ontology graph GOnt to summarize and index a data graph G iteratively, to form a hierarchical index structure G. Regarding query evaluation, we transform a keyword search q into Q according to GOnt in runtime. The transformed query is searched on the summary graphs in G. The efficiency is due to the small sizes of the summary graphs and the early pruning of semantically irrelevant subgraphs. To illustrate BiG-index's applicability, we show popular indexing techniques for keyword search can be easily implemented on top of BiG-index. Our extensive experiments show that BiG-index clearly reduced the runtimes of popular keyword search algorithms. Second, we study the problem of keyword search on public-private graph. In many applications (e.g., social networks), users may prefer to hide parts or all of her/his data graphs (e.g., private friendships) from the public. This leads to a recent graph model, namely the public-private network model, in which each user has his/her own network. While there have been studies on public-private network analysis, keyword search on public-private networks has not yet been studied. Hence, we propose a new keyword search framework, called public-private keyword search (PPKWS). PPKWS consists of three major steps: partial evaluation, answer refinement, and answer completion. We select three representative ones and show that they can be implemented on the model with minor modifications. We propose indexes and optimizations for PPKWS. We have verified through experiments that, on average, the algorithms implemented on top of PPKWS run 113 times faster than the original algorithms directly running on the public network attached to the private network for retrieving answers that span through them. Third, we study the keyword search in distributed graph evaluation systems. In the recent research on query evaluation, parallel evaluation has attracted much interest. However, the study on keyword search on distributed graphs has still been limited. We propose a novel distributed keyword search framework called DKWS. We propose a notify-push paradigm which can exchange the upper bounds of answers across all the workers asynchronously. In particular, the workers notify the coordinator when the local upper bound is refined. The coordinator pushes the refined global upper bound to all the workers. Moreover, we propose an efficient and generic keyword search algorithm for the workers. We have implemented DKWS on top of GRAPE, a distributed graph process system from our previous research collaboration. Extensive experimental results show that DKWS outperforms current-state-of-art techniques

APA, Harvard, Vancouver, ISO, and other styles

10

Lu, Linyuan Lincoln. "Probabilistic methods in massive graphs and internet computing /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2002. http://wwwlib.umi.com/cr/ucsd/fullcit?p3061653.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Ma, Zongjie. "Searching on Massive Graphs and Regularizing Deep Learning." Thesis, Griffith University, 2018. http://hdl.handle.net/10072/385875.

Full text

Abstract:

We have designed di erent heuristics for both searching on Massive graphs and regularizing Deep Neural Networks in this work. Both the problem of nding a minimum vertex cover (MinVC) and the maximum edge weight clique (MEWC) in a graph are prominent NP-hard problems of great importance in both theory and application. During recent decades, there has been much interest in nding optimal or near-optimal solutions to these two problems. Many existing heuristic algorithms for MinVC are based on local search strategies. An algorithm called FastVC takes a rst step towards solving the MinVC problem for large real-world graphs. However, FastVC may be trapped at local minima during the local search stage due to the lack of suitable diversi cation mechanisms. Besides, since the traditional best-picking heuristic was believed to be of high complexity, FastVC replaces it with an approximate best-picking strategy. However, best-picking has been proved to be robust for a wide range of problems, so abandoning it may be a great sacri ce. Therefore, we rstly design a diversi cation heuristic to help FastVC escape from local minima, and the proposed solver is named WalkVC. Secondly, we develop a local search MinVC solver, named NoiseVC, which utilizes best-picking (low complexity) with noise to remove vertices during the local search stage in massive graphs. On the other hand, most of existing heuristics for the MEWC problem focus on academic benchmarks with relatively small size. However, very little attention was paid to solving the MEWC problem in large sparse graphs. In this thesis, we exploit the so-called deterministic tournament selection (DTS) heuristic for selecting edges to improve the local search based MEWC algorithms. Deep Neural Networks (DNN), have an extremely large number of parameters comparing with traditional machine earning methods, su er from the the problem of over tting. Dropout [Hinton et al., 2012, Srivastava et al., 2014] has been proposed to address this problem. Dropout is an useful technique for regularizing and preventing the co-adaptation of neurons in DNN. It randomly drops units with a probability p during the training stage of DNN to avoid over tting. The working mechanism of dropout can be interpreted as approximately and exponentially combining many di erent neural network architectures e ciently, leading to a powerful ensemble. We propose a novel diversi cation strategy for dropout named Tabu Dropout, which aims at generating more di erent neural network architectures in fewer numbers of iterations. Besides, a recent work named Curriculum Dropout achieves the state-of-the-art performance among the dropout variants by using a scheduled p instead of a xed one. It gradually increases the dropping probability from 0 to 1 􀀀 p according to a time scheduling from curriculum learning. The primary intuition is that dropout seems unnecessary at the beginning of training and Curriculum Dropout starts training the whole neural networks without dropping, which is called \starting easy". In this thesis, we design a new scheduled dropout strategy using \starting small" instead of \starting easy", which gradually decreases the dropping probability from 1 to p. We call this strategy Annealed Curriculum Dropout. Experiments conducted on related public standard datasets show that our proposed heuristics for both searching on massive graphs and regularizing deep learning have achieved better performance than the comparison methods.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Inst Integrated&IntelligentSys
Science, Environment, Engineering and Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

12

Madduri, Kamesh. "A high-performance framework for analyzing massive complex networks." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24712.

Full text

Abstract:

Thesis (Ph.D.)--Computing, Georgia Institute of Technology, 2009.
Committee Chair: Bader, David; Committee Member: Berry, Jonathan; Committee Member: Fujimoto, Richard; Committee Member: Saini, Subhash; Committee Member: Vuduc, Richard

APA, Harvard, Vancouver, ISO, and other styles

13

Wu, Yubao. "Efficient and Effective Local Algorithms for Analyzing Massive Graphs." Case Western Reserve University School of Graduate Studies / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1454451336.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Jouili, Salim. "Indexation de masses de documents graphiques : approches structurelles." Phd thesis, Université Nancy II, 2011. http://tel.archives-ouvertes.fr/tel-00597711.

Full text

Abstract:

Les travaux de cette thèse se situent dans la cadre des approches structurelles pour la recon- naissance de formes. Plus précisément, nous avons porté notre choix sur les graphes. Le choix de la représentation structurelle est justifié par la grande capacité représentative des graphes par rapport à la représentation statistique (i.e. vecteurs). La première étape qui intervient dans l'étude de l'application des graphes dans le domaine des images est de définir une stratégie d'extraction de graphes représentatives d'images. Ensuite, il faut définir des fonctions néces- saires à la manipulation des bases de graphes. L'une des fonctions cruciales pour manipuler les graphes est la fonction de calcul des distances entre les graphes. En effet, le calcul de distances entre les graphes est un problème ouvert dans la littérature. De plus, il est considéré comme NP-complet. La plupart des solutions proposées dans la littérature présentent différentes limites d'utilisation telle que la taille des graphes, la prise en compte d'attributs, le temps de calcul. Outre la distance, le domaine des graphes souffre d'un manque d'algorithmes de classification (non-)supervisée appropriés. Dans ce sens, cette thèse présente un ensemble de contributions dont l'objectif est l'indexation de graphes. En premier lieu, nous montrons expérimentalement que choix de la représentation sous forme de graphes a un impact sur les performances. Ensuite, nous proposons une nouvelle approximation de la distance d'édition de graphes basée sur la no- tion de signature de noeuds. Nous introduisons aussi un algorithme de plongement de graphes. Cet algorithme consiste à représenter chaque graphe par un vecteur dans un espace euclidien. Ceci nous permet d'appliquer les algorithmes de classification des vecteurs sur les graphes par le biais du plongement. Dans le domaine de la classification non-supervisée (clustering), nous proposons un nouvel algorithme basé sur la notion du graphe médian et la notion du mean-shift. Enfin, nous proposons, une nouvelle méthode d'indexation de graphes basée sur la structure d'hypergraphe. Cette méthode permet aussi bien l'indexation que la navigation dans une base d'images représentées sous forme de graphes.

APA, Harvard, Vancouver, ISO, and other styles

15

Férey, Nicolas. "Exploration immersive de données génomiques textuelles et factuelles : vers une approche par visual mining." Paris 11, 2006. http://www.theses.fr/2006PA112235.

Full text

Abstract:

Ce travail de these porte sur l'exploration immersive de donnees genomiques textuelles et factuelles. Il s'agit d'etudier et de concevoir une nouvelle approche pour d'explorer dans un cadre immersif (i. E. De realite virtuelle), des donnees d'une nature specifique : les donnees genomiques. Ces donnees se presentent sous deux formes : la forme factuelle, c'est-a-dire l'ensemble des donnees structurees provenant des banques de donnees biologiques, et la forme textuelle, a savoir l'ensemble des donnees non structurees presentes dans les millions de publications concernant la genomique. Face a la complexite de ces donnees, l'enjeu est de proposer des paradigmes d'exploration et d'interaction, qui permettent de couvrir le plus largement possible ces donnees de nature variees. Ces paradigmes doivent etre capables de gerer des donnees massives, et doivent etre adaptes a la fois au cadre immersif et aux besoins des biologistes. Ainsi sur la base de l'etude des besoins des utilisateurs et de leurs usages, un paradigme de representation a ete defini en utilisant les caracteristiques tres specifiques des banques de donnees genomiques, et dans lequel la semantique des donnees etudiees est traduite par des proprietes visuelles, geometriques, ou topologiques, choisies initialement par l'utilisateur. Un prototype a ete implemente pour tester et valider le paradigme precedemment defini, et plusieurs experiences d'analyse de donnees genomiques ont ete menees en collaboration avec des biologistes ou bio-informaticiens, afin de mesurer la pertinence de cette solution d'exploration, face a plusieurs problematiques d'analyse de donnees genomiques
This thesis concerns the immersive exploration of textual and factual genomic data. The goal of this work is to design and study new approach for exploring genomic data within an immersive framework (i. E. Of virtual reality). The knowledge about genome is constituted by factual data, coming from structured biological or genomic databanks, and by textual data, namely the unstructured data within the millions publications relating to the research about genome. These data are heterogeneous, huge in quantity, and complex. The stake of this work is to propose visualization and interaction paradigms, which are able to deals with these characteristics. These paradigms must also be adapted to the immersive framework, and must respect the needs of the biologists. We used common points of genomic databanks, to design an original visualization paradigm, where the user is able to choice a translation of the semantic of the genomic data to visual, geometric or topologic properties. We implemented a software prototype in order to test and validate the visualization paradigm within an immersive framework. In this context, we proposed and tested new interaction paradigms, in order to navigate, search and edit the genomic data during the immersive exploration. We used finally this software to lead several experiments of genomic data analysis with biologists, in order to measure the relevance of this visual mining approach on different kinds of genomic data

APA, Harvard, Vancouver, ISO, and other styles

16

Sansen, Joris. "La visualisation d’information pour les données massives : une approche par l’abstraction de données." Thesis, Bordeaux, 2017. http://www.theses.fr/2017BORD0636/document.

Full text

Abstract:

L’évolution et la démocratisation des technologies ont engendré une véritable explosion de l’information et notre capacité à générer des données et le besoin de les analyser n’a jamais été aussi important. Pourtant, les problématiques soulevées par l’accumulation de données (stockage, temps de traitement, hétérogénéité, vitesse de captation/génération, etc. ) sont d’autant plus fortes que les données sont massives, complexes et variées. La représentation de l’information, de part sa capacité à synthétiser et à condenser des données, se constitue naturellement comme une approche pour les analyser mais ne résout pas pour autant ces problèmes. En effet, les techniques classiques de visualisation sont rarement adaptées pour gérer et traiter cette masse d’informations. De plus,les problèmes que soulèvent le stockage et le temps de traitement se répercutent sur le système d’analyse avec par exemple, la distanciation de plus en plus forte entre la donnée et l’utilisateur : le lieu où elle sera stockée et traitée et l’interface utilisateur servant à l’analyse. Dans cette thèse nous nous intéressons à ces problématiques et plus particulièrement à l’adaptation des techniques de visualisation d’informations pour les données massives. Pour cela, nous nous intéressons tout d’abord à l’information de relation entre éléments, comment est-elle véhiculée et comment améliorer cette transmission dans le contexte de données hiérarchisées. Ensuite, nous nous intéressons à des données multivariées,dont la complexité à un impact sur les calculs possibles. Enfin, nous présentons les approches mises en oeuvre pour rendre nos méthodes compatibles avec les données massives
The evolution and spread of technologies have led to a real explosion of information and our capacity to generate data and our need to analyze them have never been this strong. Still, the problems raised by such accumulation (storage, computation delays, diversity, speed of gathering/generation, etc. ) is as strong as the data are big, complex and varied. Information visualization,by its ability to summarize and abridge data was naturally established as appropriate approach. However, it does not solve the problem raised by Big Data. Actually, classical visualization techniques are rarely designed to handle such mass of information. Moreover, the problems raised by data storage and computation time have repercussions on the analysis system. For example,the increasing distance between the data and the analyst : the place where the data is stored and the place where the user will perform the analyses arerarely close. In this thesis, we focused on these issues and more particularly on adapting the information visualization techniques for Big Data. First of all focus on relational data : how does the existence of a relation between entity istransmitted and how to improve this transmission for hierarchical data. Then,we focus on multi-variate data and how to handle their complexity for the required computations. Finally, we present the methods we designed to make our techniques compatible with Big Data

APA, Harvard, Vancouver, ISO, and other styles

17

Echbarthi, Ghizlane. "Big Graph Processing : Partitioning and Aggregated Querying." Thesis, Lyon, 2017. http://www.theses.fr/2017LYSE1225/document.

Full text

Abstract:

Avec l'avènement du « big data », de nombreuses répercussions ont eu lieu dans tous les domaines de la technologie de l'information, préconisant des solutions innovantes remportant le meilleur compromis entre coûts et précision. En théorie des graphes, où les graphes constituent un support de modélisation puissant qui permet de formaliser des problèmes allant des plus simples aux plus complexes, la recherche pour des problèmes NP-complet ou NP-difficils se tourne plutôt vers des solutions approchées, mettant ainsi en avant les algorithmes d'approximations et les heuristiques alors que les solutions exactes deviennent extrêmement coûteuses et impossible d'utilisation.Nous abordons dans cette thèse deux problématiques principales: dans un premier temps, le problème du partitionnement des graphes est abordé d'une perspective « big data », où les graphes massifs sont partitionnés en streaming. Nous étudions et proposons plusieurs modèles de partitionnement en streaming et nous évaluons leurs performances autant sur le plan théorique qu'empirique. Dans un second temps, nous nous intéressons au requêtage des graphes distribués/partitionnés. Dans ce cadre, nous étudions la problématique de la « recherche agrégative dans les graphes » qui a pour but de répondre à des requêtes interrogeant plusieurs fragments de graphes et qui se charge de la reconstruction de la réponse finale tel que l'on obtient un « matching approché » avec la requête initiale
With the advent of the "big data", many repercussions have taken place in all fields of information technology, advocating innovative solutions with the best compromise between cost and accuracy. In graph theory, where graphs provide a powerful modeling support for formalizing problems ranging from the simplest to the most complex, the search for NP-complete or NP-difficult problems is rather directed towards approximate solutions, thus Forward approximation algorithms and heuristics while exact solutions become extremely expensive and impossible to use. In this thesis we discuss two main problems: first, the problem of partitioning graphs is approached from a perspective big data, where massive graphs are partitioned in streaming. We study and propose several models of streaming partitioning and we evaluate their performances both theoretically and empirically. In a second step, we are interested in querying distributed / partitioned graphs. In this context, we study the problem of aggregative search in graphs, which aims to answer queries that interrogate several fragments of graphs and which is responsible for reconstructing the final response such that a Matching approached with the initial query

APA, Harvard, Vancouver, ISO, and other styles

18

Castelltort, Arnaud. "Historisation de données dans les bases de données NoSQLorientées graphes." Thesis, Montpellier 2, 2014. http://www.theses.fr/2014MON20076.

Full text

Abstract:

Cette thèse porte sur l'historisation des données dans les bases de données graphes. La problématique des données en graphes existe depuis longtemps mais leur exploitation par des moteurs de système de gestion de bases de données, principalement dans les moteurs NoSQL, est récente. Cette apparition est notamment liée à l'émergence des thématiques Big Data dont les propriétés intrinsèques, souvent décrites à l'aide des propriétés 3V (variété, volume, vélocité), ont révélé les limites des bases de données relationnelles classiques. L'historisation quant à elle, est un enjeu majeur des SI qui a été longtemps abordé seulement pour des raisons techniques de sauvegarde, de maintenance ou plus récemment pour des raisons décisionnelles (suites applicatives de Business Intelligence). Cependant, cet aspect s'avère maintenant prendre une place prédominante dans les applications de gestion. Dans ce contexte, les bases de données graphes qui sont de plus en plus utilisées n'ont que très peu bénéficié des apports récents de l'historisation. La première contribution consiste à étudier le nouveau poids des données historisées dans les SI de gestion. Cette analyse repose sur l'hypothèse selon laquelle les applications de gestion intègrent de plus en plus en leur sein les enjeux d'historisation. Nous discutons ce positionnement au regard de l'analyse de l'évolution des SI par rapport à cette problématique. La deuxième contribution vise, au-delà de l'étude de l'évolution des sytèmes d'information, à proposer un modèle innovant de gestion de l'historisation dans les bases de données NoSQL en graphes. Cette proposition consiste d'une part en l'élaboration d'un système unique et générique de représentation de l'historique au sein des BD NoSQL en graphes et d'autre part à proposer des modes d'interrogation (requêtes). Nous montrons qu'il est possible d'utiliser ce système aussi bien pour des requêtes simples (c'est-à-dire correspondant à ce que l'on attend en première intention d'un système d'historisation~: récupérer les précédentes versions d'une donnée) mais aussi de requêtes plus complexes qui permettent de tirer parti aussi bien de la notion d'historisation que des possibilités offertes par les bases de données graphes (par exemple, la reconnaissance de motifs dans le temps)
This thesis deals with data historization in the context of graphs. Graph data have been dealt with for many years but their exploitation in information systems, especially in NoSQL engines, is recent. The emerging Big Data and 3V contexts (Variety, Volume, Velocity) have revealed the limits of classical relational databases. Historization, on its side, has been considered for a long time as only linked with technical and backups issues, and more recently with decisional reasons (Business Intelligence). However, historization is now taking more and more importance in management applications.In this framework, graph databases that are often used have received little attention regarding historization. Our first contribution consists in studying the impact of historized data in management information systems. This analysis relies on the hypothesis that historization is taking more and more importance. Our second contribution aims at proposing an original model for managing historization in NoSQL graph databases.This proposition consists on the one hand in elaborating a unique and generic system for representing the history and on the other hand in proposing query features.We show that the system can support both simple and complex queries.Our contributions have been implemented and tested over synthetic and real databases

APA, Harvard, Vancouver, ISO, and other styles

19

Deri, Joya A. "Graph Signal Processing: Structure and Scalability to Massive Data Sets." Research Showcase @ CMU, 2016. http://repository.cmu.edu/dissertations/725.

Full text

Abstract:

Large-scale networks are becoming more prevalent, with applications in healthcare systems, financial networks, social networks, and traffic systems. The detection of normal and abnormal behaviors (signals) in these systems presents a challenging problem. State-of-the-art approaches such as principal component analysis and graph signal processing address this problem using signal projections onto a space determined by an eigendecomposition or singular value decomposition. When a graph is directed, however, applying methods based on the graph Laplacian or singular value decomposition causes information from unidirectional edges to be lost. Here we present a novel formulation and graph signal processing framework that addresses this issue and that is well suited for application to extremely large, directed, sparse networks. In this thesis, we develop and demonstrate a graph Fourier transform for which the spectral components are the Jordan subspaces of the adjacency matrix. In addition to admitting a generalized Parseval’s identity, this transform yields graph equivalence classes that can simplify the computation of the graph Fourier transform over certain networks. Exploration of these equivalence classes provides the intuition for an inexact graph Fourier transform method that dramatically reduces computation time over real-world networks with nontrivial Jordan subspaces. We apply our inexact method to four years of New York City taxi trajectories (61 GB after preprocessing) over the NYC road network (6,400 nodes, 14,000 directed edges). We discuss optimization strategies that reduce the computation time of taxi trajectories from raw data by orders of magnitude: from 3,000 days to less than one day. Our method yields a fine-grained analysis that pinpoints the same locations as the original method while reducing computation time and decreasing energy dispersal among spectral components. This capability to rapidly reduce raw traffic data to meaningful features has important ramifications for city planning and emergency vehicle routing.

APA, Harvard, Vancouver, ISO, and other styles

20

Ben, Dhia Imen. "Gestion des grandes masses de données dans les graphes réels." Thesis, Paris, ENST, 2013. http://www.theses.fr/2013ENST0087/document.

Full text

Abstract:

De nos jours, un grand nombre d’applications utilisent de grands graphes pour la modélisation de données du monde réel. Nous avons assisté, ces dernières années, à une très rapide croissance de ces graphes dans divers contextes ; à savoir, les réseaux sociaux, la bioinformatique, le web sémantique, les systèmes de gestion des données géographiques, etc. La gestion, l’analyse et l’interrogation de ces données constituent un enjeu très important et ont suscité un vaste intérêt dans la communauté des Bases de Données. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’indexation et l’interrogation des données dans les grands graphes. Nous avons proposé EUQLID, une technique d’indexation qui permet de répondre efficacement aux requêtes de calcul de distance dans les grands graphes orientés. L’efficacité de cette technique est dûe au fait qu’elle exploite des propriétés intéressantes des graphes du monde réel. En effet, nous proposons un algorithme basé sur une variante efficace du fameux algorithme 2-hop. Les résultats obtenus montrent que notre algorithme surpassent les approches existantes en terme de temps d’indexation, ainsi qu’en temps de réponse. En effet, il permet de calculer la distance entre deux noeuds en quelques centaines de millisecondes sur de très grands graphes. Nous proposons également un modèle de contrôle d’accès pour les réseaux sociaux qui permet aux utlisateurs de spécifier leurs poltiques de contrôle d’accès en se basant sur leurs relations sociales, et qui peut utiliser EUQLID pour passer à l’échelle. Nous décrivons Primates comme étant un prototype appliquant le modèle proposé
In the last few years, we have been witnessing a rapid growth of networks in a wide range of applications such as social networking, bio-informatics, semantic web, road maps, etc. Most of these networks can be naturally modeled as large graphs. Managing, analyzing, and querying such data has become a very important issue, and, has inspired extensive interest within the database community. In this thesis, we address the problem of efficiently answering distance queries in very large graphs. We propose EUQLID, an efficient algorithm to answer distance queries on very large directed graphs. This algorithm exploits some interesting properties that real-world graphs exhibit. It is based on an efficient variant of the seminal 2-hop algorithm. We conducted an extensive set of experiments against state-of-the-art algorithms which show that our approach outperforms existing approaches and that distance queries can be processed within hundreds of milliseconds on very large real-world directed graphs. We also propose an access control model for social networks which can make use of EUQLID to scale on very large graphs. This model allows users to specify fine-grained privacy policies based on their relations with other users in the network. We describe and demonstrate Primates as a prototype which enforces the proposed access control model and allows users to specify their privacy preferences via a graphical user-friendly interface

APA, Harvard, Vancouver, ISO, and other styles

21

Ben, Dhia Imen. "Gestion des grandes masses de données dans les graphes réels." Electronic Thesis or Diss., Paris, ENST, 2013. http://www.theses.fr/2013ENST0087.

Full text

Abstract:

De nos jours, un grand nombre d’applications utilisent de grands graphes pour la modélisation de données du monde réel. Nous avons assisté, ces dernières années, à une très rapide croissance de ces graphes dans divers contextes ; à savoir, les réseaux sociaux, la bioinformatique, le web sémantique, les systèmes de gestion des données géographiques, etc. La gestion, l’analyse et l’interrogation de ces données constituent un enjeu très important et ont suscité un vaste intérêt dans la communauté des Bases de Données. L’objectif de cette thèse est de fournir des algorithmes efficaces pour l’indexation et l’interrogation des données dans les grands graphes. Nous avons proposé EUQLID, une technique d’indexation qui permet de répondre efficacement aux requêtes de calcul de distance dans les grands graphes orientés. L’efficacité de cette technique est dûe au fait qu’elle exploite des propriétés intéressantes des graphes du monde réel. En effet, nous proposons un algorithme basé sur une variante efficace du fameux algorithme 2-hop. Les résultats obtenus montrent que notre algorithme surpassent les approches existantes en terme de temps d’indexation, ainsi qu’en temps de réponse. En effet, il permet de calculer la distance entre deux noeuds en quelques centaines de millisecondes sur de très grands graphes. Nous proposons également un modèle de contrôle d’accès pour les réseaux sociaux qui permet aux utlisateurs de spécifier leurs poltiques de contrôle d’accès en se basant sur leurs relations sociales, et qui peut utiliser EUQLID pour passer à l’échelle. Nous décrivons Primates comme étant un prototype appliquant le modèle proposé
In the last few years, we have been witnessing a rapid growth of networks in a wide range of applications such as social networking, bio-informatics, semantic web, road maps, etc. Most of these networks can be naturally modeled as large graphs. Managing, analyzing, and querying such data has become a very important issue, and, has inspired extensive interest within the database community. In this thesis, we address the problem of efficiently answering distance queries in very large graphs. We propose EUQLID, an efficient algorithm to answer distance queries on very large directed graphs. This algorithm exploits some interesting properties that real-world graphs exhibit. It is based on an efficient variant of the seminal 2-hop algorithm. We conducted an extensive set of experiments against state-of-the-art algorithms which show that our approach outperforms existing approaches and that distance queries can be processed within hundreds of milliseconds on very large real-world directed graphs. We also propose an access control model for social networks which can make use of EUQLID to scale on very large graphs. This model allows users to specify fine-grained privacy policies based on their relations with other users in the network. We describe and demonstrate Primates as a prototype which enforces the proposed access control model and allows users to specify their privacy preferences via a graphical user-friendly interface

APA, Harvard, Vancouver, ISO, and other styles

22

Baalbaki, Hussein. "Designing Big Data Frameworks for Quality-of-Data Controlling in Large-Scale Knowledge Graphs." Electronic Thesis or Diss., Sorbonne université, 2023. http://www.theses.fr/2023SORUS697.

Full text

Abstract:

Les Knowledge Graphs (KG) sont la représentation la plus utilisée d'informations structurées sur un domaine particulier, composée de milliards de faits sous la forme d'entités (nœuds) et de relations (bords) entre eux. De plus, les informations de type sémantique des entités sont également contenues dans les KG. Le nombre de KG n'a cessé d'augmenter au cours des 20 dernières années dans divers domaines, notamment le gouvernement, la recherche universitaire, les domaines biomédicaux, etc. Les applications basées sur l'apprentissage automatique qui utilisent les KG incluent la liaison d'entités, les systèmes de questions-réponses, les systèmes de recommandation, etc. Les Open KG sont généralement produits de manière heuristique, automatiquement à partir de diverses sources, notamment du texte, des photos et d'autres ressources, ou sont sélectionnés manuellement. Cependant, ces KG sont souvent incomplètes, c'est-à-dire qu'il existe des liens manquants entre les entités et des liens manquants entre les entités et leurs types d'entités correspondants. Dans cette thèse, nous abordons l’un des problèmes les plus difficiles auxquels est confronté le Knowledge Graph Completion (KGC), à savoir la prédiction de liens. Prédiction générale des liens en KG qui inclut la prédiction de la tête et de la queue, triple classification. Ces dernières années, les KGE ont été formés pour représenter les entités et les relations du KG dans un espace vectoriel de faible dimension préservant la structure du graphe. Dans la plupart des travaux publiés tels que les modèles translationnels, les modèles de réseaux neuronaux et autres, la triple information est utilisée pour générer la représentation latente des entités et des relations. Dans cette thèse, plusieurs méthodes ont été proposées pour KGC et leur efficacité est démontrée empiriquement dans cette thèse. Tout d’abord, un nouveau modèle d’intégration KG, TransModE, est proposé pour la prédiction de liens. TransModE projette les informations contextuelles des entités dans un espace modulaire, tout en considérant la relation comme vecteur de transition qui guide l'entité tête vers l'entité queue. Deuxièmement, nous avons travaillé sur la construction d'un modèle KGE simple et de faible complexité, tout en préservant son efficacité. KEMA est un nouveau modèle KGE parmi les modèles KGE les plus bas en termes de complexité, tout en obtenant des résultats prometteurs. Enfin, KEMA++ est proposé comme une mise à niveau de KEMA pour prédire les triplets manquants dans les KG en utilisant l'opération arithmétique des produits dans un espace modulaire. Les expériences approfondies et les études d'ablation montrent l'efficacité du modèle proposé, qui rivalise avec les modèles de pointe actuels et établit de nouvelles références pour KGC
Knowledge Graphs (KGs) are the most used representation of structured information about a particular domain consisting of billions of facts in the form of entities (nodes) and relations (edges) between them. Additionally, the semantic type information of the entities is also contained in the KGs. The number of KGs has steadily increased over the past 20 years in a variety of fields, including government, academic research, the biomedical fields, etc. Applications based on machine learning that use KGs include entity linking, question-answering systems, recommender systems, etc. Open KGs are typically produced heuristically, automatically from a variety of sources, including text, photos, and other resources, or are hand-curated. However, these KGs are often incomplete, i.e., there are missing links between the entities and missing links between the entities and their corresponding entity types. In this thesis, we are addressing one of the most challenging issues facing Knowledge Graph Completion (KGC) which is link prediction. General Link Prediction in KGs that include head and tail prediction, triple classification. In recent years, KGE have been trained to represent the entities and relations in the KG in a low-dimensional vector space preserving the graph structure. In most published works such as the translational models, neural network models and others, the triple information is used to generate the latent representation of the entities and relations. In this dissertation, several methods have been proposed for KGC and their effectiveness is shown empirically in this thesis. Firstly, a novel KG embedding model TransModE is proposed for Link Prediction. TransModE projects the contextual information of the entities to modular space, while considering the relation as transition vector that guide the head to the tail entity. Secondly, we worked on building a simple low complexity KGE model, meanwhile preserving its efficiency. KEMA is a novel KGE model among the lowest KGE models in terms of complexity, meanwhile it obtains promising results. Finally, KEMA++ is proposed as an upgrade of KEMA to predict the missing triples in KGs using product arithmetic operation in modular space. The extensive experiments and ablation studies show efficiency of the proposed model, which compete the current state of the art models and set new baselines for KGC. The proposed models establish new way in solving KGC problem other than transitional, neural network, or tensor factorization based approaches. The promising results and observations open up interesting scopes for future research involving exploiting the proposed models in domain-specific KGs such as scholarly data, biomedical data, etc. Furthermore, the link prediction model can be exploited as a base model for the entity alignment task as it considers the neighborhood information of the entities

APA, Harvard, Vancouver, ISO, and other styles

23

Gilbert, Frédéric. "Méthodes et modèles pour la visualisation de grandes masses de données multidimensionnelles nominatives dynamiques." Thesis, Bordeaux 1, 2012. http://www.theses.fr/2012BOR14498/document.

Full text

Abstract:

La visualisation d'informations est un domaine qui connaît un réel intérêt depuis une dizaine d'années. Dernièrement, avec l'explosion des moyens de communication, l'analyse de réseaux sociaux fait l'objet de nombreux travaux de recherches. Nous présentons dans cette thèse des travaux sur l'analyse de réseaux sociaux dynamiques, c'est à dire que nous prenons en compte l'aspect temporel des données. [...]
Since ten years, informations visualization domain knows a real interest.Recently, with the growing of communications, the research on social networks analysis becomes strongly active. In this thesis, we present results on dynamic social networks analysis. That means that we take into account the temporal aspect of data. We were particularly interested in communities extraction within networks and their evolutions through time. [...]

APA, Harvard, Vancouver, ISO, and other styles

24

Bordairon, Marc. "Dimensionnement des massifs en sol renforcé par géosynthétiques." Grenoble INPG, 1986. http://www.theses.fr/1986INPG0113.

Full text

Abstract:

Calcul des massifs de soutenement en terre renforcee par des nappes horizontales de geosynthetiques. Analyse detaillee d'une nouvelle "methode double blocs" et formalisee par une geometrie quelconque et des sollicitations diverses. Surface de glissement polygonale. Etude de l'influence de certains parametres (hauteur, sol, inclinaison du parement) sur le dimensionnement en vue de l'elaboration d'abaques de dimensionnement de massifs en sol renforce que l'on presente. Comparaison avec des methodes d'equilibre limite a surface de glissement circulaire. Resume des principales methodes traditionnelles pour des massifs a parements verticaux. Application de ces methodes sur des ouvrages de soutenement construits dans le departement de l'isere

APA, Harvard, Vancouver, ISO, and other styles

25

Scotti, Andrea. "Graph Neural Networks and Learned Approximate Message Passing Algorithms for Massive MIMO Detection." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2020. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-284500.

Full text

Abstract:

Massive multiple-input and multiple-output (MIMO) is a method to improvethe performance of wireless communication systems by having a large numberof antennas at both the transmitter and the receiver. In the fifth-generation(5G) mobile communication system, Massive MIMO is a key technology toface the increasing number of mobile users and satisfy user demands. At thesame time, recovering the transmitted information in a massive MIMO uplinkreceiver requires more computational complexity when the number of transmittersincreases. Indeed, the optimal maximum likelihood (ML) detector hasa complexity exponentially increasing with the number of transmitters. Therefore,one of the main challenges in the field is to find the best sub-optimalMIMO detection algorithm according to the performance/complexity tradeoff.In this work, all the algorithms are empirically evaluated for large MIMOsystems and higher-order modulations.Firstly, we show how MIMO detection can be represented by a MarkovRandom Field (MRF) and addressed by the loopy belief propagation (LBP)algorithm to approximately solve the equivalent MAP (maximum a posteriori)inference problem. Then, we propose a novel algorithm (BP-MMSE) thatstarts from the minimum mean square error (MMSE) solution and updates theprior in each iteration with the LBP belief. To avoid the complexity of computingMMSE, we use Graph Neural Networks (GNNs) to learn a messagepassingalgorithm that solves the inference task on the same graph.To further reduce the complexity of message-passing algorithms, we recallhow in the large system limit, approximate message passing (AMP), a lowcomplexity iterative algorithm, can be derived from LBP to solve MIMO detectionfor i.i.d. Gaussian channels. Then, we show numerically how AMPwith damping (DAMP) can be robust to low/medium correlation among thechannels. To conclude, we propose a low complexity deep neural iterativescheme (Pseudo-MMNet) for solvingMIMOdetection in the presence of highlycorrelated channels at the expense of online training for each channel realization.Pseudo-MMNet is based on MMNet algorithm presented in [24] (in turnbased on AMP) and it significantly reduces the online training complexity thatmakes MMNet far from realistic implementations.
Massiv MIMO (multiple-input and multiple-output) är en metod som förbättrarprestandan i trådlösa kommunikationssystem genom att ett stort antal antenneranvänds i både sändare och mottagare. I den femte generationens (5G)mobila kommunikationssystem är Massiv MIMO en mycket viktig teknologiför att möta det växande antalet mobilanvändare och tillgodose användarnasbehov. Samtidigt ökar beräkningskomplexiteten för att återfinna den överfördainformationen i en trådlös Massiv MIMO-upplänk när antalet antenner ökar.Faktum är att den optimala ML-detektorn (maximum likelihood) har en beräkningskomplexitetsom ökar exponentiellt med antalet sändare. En av huvudutmaningarnainom detta område är därför att hitta den bästa suboptimalaMIMO-detekteringsalgoritmen med hänsyn till både prestanda och komplexitet.I detta arbete visar vi hur MIMO-detektering kan representeras av ett MarkovRandom Field (MRF) och använder loopy belief-fortplantning (LBP) föratt lösa det motsvarande MAP-slutledningsproblemet (maximum a posteriori).Vi föreslår sedan en ny algoritm (BP-MMSE) som kombinerar LBP ochMMSE (minimum mean square error) för att lösa problemet vid högre modulationsordningarsom QAM-16 (kvadratamplitudsmodulation) och QAM-64.För att undvika komplexiteten med att beräkna MMSE så använder vi oss avgraf neurala nätverk (GNN) för att lära en message-passing algoritm som löserslutledningsproblemet med samma graf. En message-passing algoritm måstegiven en komplett graf utbyta kvadraten av antalet noder meddelanden. För attminska message-passing algoritmers beräkningskomplexitet vet vi att approximativmessage-passing (AMP) kan härledas från LBP i gränsvärdet av storasystem för att lösa MIMO-detektering med oberoende och likafördelade (i.i.d)Gaussiska kanaler. Vi visar sedan hur AMP med dämpning (DAMP) kan vararobust med låg- till mellan-korrelerade kanaler.Avslutningsvis föreslår vi en iterativ djup neuralt nätverk algoritm medlåg beräkningskomplexitet (Pseudo-MMNet) för att lösa MIMO-detektering ikanaler med hög korrelation på bekostnad av online-träning för varje realiseringav kanalen. Pseudo-MMNet är baserad på MMnet som presenteras i [23](istället för AMP) och minskar signifikant online-träningskomplexiteten somgör MMNet orealistisk att använda. Alla föreslagna algoritmer är empirisktutvärderade för stora MIMO-system och högre ordningar av modulation.

APA, Harvard, Vancouver, ISO, and other styles

26

Tavares, Mauro. "Etude du comportement tribologique des couples feutres abradables : alliages refractaires massifs à faible et grande vitesse de glissement." Toulouse, INPT, 1987. http://www.theses.fr/1987INPT044G.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Tavares, Mauro. "Etude du comportement tribologique des couples feutres abradables alliages réfractaires massifs à faible et grande vitesse de glissement /." Grenoble 2 : ANRT, 1987. http://catalogue.bnf.fr/ark:/12148/cb37610202t.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Farina, Sofia. "A physical interpretation of network laplacian: role of perturbations and masses." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2018. http://amslaurea.unibo.it/16345/.

Full text

Abstract:

Il presente elaborato si propone di studiare il laplaciano associato ad un network, oggetto di interesse sia perchè dalla sua analisi spettrale è possibile ricavare delle tecniche di ricostruzione e rappresentazione della rete efficienti e al contempo semplici da implementare, ma anche per la sua possibile intepretazione fisica. Il lavoro si struttura in due sezioni: la prima, riguardante l'analisi numerica dello spettro del laplaciano di un network con particolari proprietà di simmetria e regolarità anche in seguito alla sua perturbazione in termini di rimozone casuale di nodi e di link; la seconda incentrata su un suo modello intepretativo in chiave fisica che ci permette di ragionare sul reticolo immaginandolo come una serie di masse collegate tra loro da molle, dotate di una lunghezza caratteristica e di una costante elastica, e di vedere la sua rappresentazione come la visualizzazione dello stato di equilibrio raggiunto da questo sistema.

APA, Harvard, Vancouver, ISO, and other styles

29

BOUGNOUX, ANNE. "Modelisation thermo-hydro-mecanique des massifs fractures a moyenne ou grande echelle simulation micro-macro du comportement mecanique des fractures." Paris, ENMP, 1995. http://www.theses.fr/1995ENMP0583.

Full text

Abstract:

Le stockage de dechets nucleaires en milieu naturel fracture pose deux problemes majeurs: comment le massif reagit-il a la forte sollicitation thermique et comment eviter la contamination des eaux souterraines ainsi que le transport de particules radioactives vers la biosphere ? les phenomenes mis en jeu sont tres complexes a cause des couplages entre les aspects thermiques, mecaniques et hydrauliques. En dehors de l'experimentation in-situ, les principaux moyens d'etude de ces problemes sont la modelisation et la simulation numerique. En general, les etudes concernant les massifs rocheux se font selon une approche de type milieu continu equivalent. Or, l'analyse des ecoulements et de la connectivite des fractures impose le choix d'une approche discrete. Le premier but de notre travail est de demontrer la faisabilite de cette approche discrete. Nous montrons ses apports par comparaison au milieu continu equivalent (irreversibilite des deformations, connectivite) et prouvons sur un modele en vraie grandeur que les aspects numeriques, sans etre negligeables, ne limitent pas considerablement sa mise en uvre. Par ailleurs, nous montrons que le couplage numerique donne d'excellents resultats, tout en permettant de resoudre des sous-problemes beaucoup moins complexes que le probleme initial. Dans une approche discrete, il faut un bon modele de fractures, tout particulierement pour l'etude des phenomenes hydrauliques en general, et a moyenne echelle en particulier. En effet, les debits etant le plus souvent calcules en fonction du cube de l'ouverture des fractures, il est particulierement important de calculer cette derniere quantite avec precision. Pour ce faire, et c'est le second objectif de notre recherche, nous avons choisi une approche micro-macro pour decrire le comportement d'une fracture. Cela permet d'etudier la destruction de la rugosite des epontes, qui est la principale responsable des variations d'ouverture. Pour cela, nous etudions d'abord le comportement d'une asperite isolee, puis nous observons les interactions entre asperites dans une fracture a morphologie de plus en plus complexe. Les effets d'echelle et les aspects tridimensionnels pourront etre pris en compte par une description adequate de la rugosite

APA, Harvard, Vancouver, ISO, and other styles

30

ABDESSELAM, MALEK. "Structure et fonctionnement d'un karst de montagne sous climat mediterraneen : exemple du djurdjura occidental (grande kabylie algerie)." Besançon, 1995. http://www.theses.fr/1995BESA2068.

Full text

Abstract:

La chaine du djurdjura (2308 m) est situee en bordure de la mediterranee a l'est d'alger. Elle est formee par un empilement d'ecailles, allongees dans la direction est-ouest, dominees par les calcaires massifs du lias inferieur et de l'eocene. La karstification est importante de type haut-alpin avec de grandes cavites et drains verticaux guides par la structure geologique. Les precipitations (plus de 1200 mm/an a tala guilef et plus de 1500 mm aux sommets), sont a plus de 50% neigeuses en altitude. La fusion nivale produit des lames d'eau etalee dans le tempse et alimente l'infiltration. Le debit moyen a l'exutoire principal (tinzert) est de 424 l/s. Le debit d'etiage est de 87 l/s. Au vu de sa superficie (11 km#2) et de la longueur de la saison seche (3-4 mois), ce debit est particulierement soutenu. L'etude hydrodynamique a montre un fonctionnement complexe lie a la structure geologique, au regime climatique et a la nature des precipitations. Il possede une structure favorable a un piegeage important des eaux en surface par la retention nivale, et dans l'aquifere avec des decrues longues. Le coefficient de tarissement est faible (entre 0,0014 et 0,0053). Les tracages montrent des vitesses de circulation des eaux faibles (50 m/h). Le karst profond encore peu developpe semble capacitif. Le volume dynamique annuel est de trois millions de metres cube. Le facies des eaux est bicarbonate calcique a la majorite des sources. Il est chlorure sodique a tinzert. Ce caractere, associe a la presence du strontium, montre qu'en profondeur, l'ecoulement est controle par du trias evaporitique. L'analyse multidimensionnelle des donnees hydro-chimiques, a permis de rattacher les differentes sources a des unites structurales distinctes. Elles constitueraient des ensembles hydrogeologiques independants comme releves par les experiences de tracage et les analyses isotopiques. Les reserves peuvent etres importantes en aval dans des terrains du pourtour des massifs et des structures capacitives comme le karst noye, les accumulations de glaciers rocheux et les conglomerats de l'eo-oligocene

APA, Harvard, Vancouver, ISO, and other styles

31

Simon, Laurent. "Recherches biogéographiques en forêt de Coucy-Basse (Aisne) : cartographie thématique à grande échelle d'un massif forestier." Paris 1, 1988. http://www.theses.fr/1988PA010507.

Full text

Abstract:

Ce travail aborde les problemes de cartographie biogeographique a grande echelle dans un milieu tempere de plaine particulierement diversifie. Apres avoir analyse les principaux facteurs de cette diversite naturelle, l'etude s'attache a decrire les grandes caracteristiques du paysage forestier. Elles sont dans une large mesure le resultat des interventions anthropiques sur le milieu. Ce sont notamment les consequences de la premiere guerre mondiale qui expliquent le paysage actuel de la foret et la composition de la strate arboree. Les evenements historiques sont responsables de la hauteur limitee de la voute arboree et de l'importance du charme et du bouleau. Ainsi la composition de la foret traduit en fait les evenements historiques plus ou moins anciens. La cartographie a grande echelle permet egalement de nuancer l'idee couramment admise d'une foret dominee par le hetre. Il s'agit en realite d'un ensemble beaucoup plus composite. Ce caractere diversifie se retrouve lorsque l'on etudie les groupements vegetaux et les conditions ecologiques qu'ils indiquent. La foret de coucy-basse apparait comme une veritable mosaique de groupements aux exigences tres diverses. Seule une cartographie a grande echelle peut en rendre compte et mettre en evidence les relations spatiales qui existent entre les principaux groupements. Certaines especes rares ou en limite de leur aire d'extension temoignent enfin de la richesse biogeographique de cet ensemble situe aux limites de plusieurs domaines phytogeographiques. L'etude souligne egalement les elements de dynamisme qui caracterisent ce massif forestier.

APA, Harvard, Vancouver, ISO, and other styles

32

Simon, Laurent. "Recherches biogéographiques en forêt de Coucy-Basse, Aisne cartographie thématique à grande échelle d'un massif forestier /." Lille 3 : ANRT, 1989. http://catalogue.bnf.fr/ark:/12148/cb37618548w.

Full text

APA, Harvard, Vancouver, ISO, and other styles

33

Yoon, Hosang. "Two-Dimensional Plasmonics in Massive and Massless Electron Gases." Thesis, Harvard University, 2014. http://nrs.harvard.edu/urn-3:HUL.InstRepos:13070026.

Full text

Abstract:

Plasmonic waves in solid-state are caused by collective oscillation of mobile charges inside or at the surface of conductors. In particular, surface plasmonic waves propagating at the skin of metals have recently attracted interest, as they reduce the wavelength of electromagnetic waves coupled to them by up to ~10 times, allowing one to create miniaturized wave devices at optical frequencies. In contrast, plasmonic waves on two-dimensional (2D) conductors appear at much lower infrared and THz-GHz frequencies, near or in the electronics regime, and can achieve far stronger wavelength reduction factor reaching well above 100. In this thesis, we study the unique machinery of 2D plasmonic waves behind this ultra-subwavelength confinement and explore how it can be used to create various interesting devices. To this end, we first develop a physically intuitive theoretical formulation of 2D plasmonic waves, whose two main components---the Coulomb restoration force and inertia of the collectively oscillating charges---are combined into a transmission-line-like model. We then use this formulation to create various ultra-subwavelength 2D plasmonic devices. For the 2D conductor, we first choose GaAs/AlGaAs heterostructure---a 2D electron gas consisting of massive (m*>0) electrons---demonstrating plasmonic bandgap crystals, interferometers, and negatively refracting metamaterials. We then examine a 2D plasmonic device based on graphene, a 2D electron gas consisting of effectively massless (m*=0) electrons. We theoretically show and experimentally demonstrate that the massless electrons in graphene can surprisingly exhibit a collective mass when subjected to a collective excitation, providing the inertia that is essential for the propagation of 2D plasmonic waves. Lastly, we theoretically investigate the thermal current fluctuation behaviors in massive and massless electron gases. While seemingly unrelated on first sight, we show that the thermal current fluctuation is actually intimately linked to the collective mass of the massive or massless electron gas. Thus, we show that the thermal current fluctuation behaviors can also be described by the same theoretical framework introduced earlier, suggesting a possibility to design new concept devices and experiments based on this linkage.
Engineering and Applied Sciences

APA, Harvard, Vancouver, ISO, and other styles

34

Perez, Postigo Lorgio Victoriano. "Contribution à l'étude géologique du subbriançonnais entre Arc et Isère. Les massifs du Perron des Encombres et de la Grande Moendaz." Chambéry, 1988. http://www.theses.fr/1988CHAMA002.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Agarwal, Virat. "Algorithm design on multicore processors for massive-data analysis." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/34839.

Full text

Abstract:

Analyzing massive-data sets and streams is computationally very challenging. Data sets in systems biology, network analysis and security use network abstraction to construct large-scale graphs. Graph algorithms such as traversal and search are memory-intensive and typically require very little computation, with access patterns that are irregular and fine-grained. The increasing streaming data rates in various domains such as security, mining, and finance leaves algorithm designers with only a handful of clock cycles (with current general purpose computing technology) to process every incoming byte of data in-core at real-time. This along with increasing complexity of mining patterns and other analytics puts further pressure on already high computational requirement. Processing streaming data in finance comes with an additional constraint to process at low latency, that restricts the algorithm to use common techniques such as batching to obtain high throughput. The primary contributions of this dissertation are the design of novel parallel data analysis algorithms for graph traversal on large-scale graphs, pattern recognition and keyword scanning on massive streaming data, financial market data feed processing and analytics, and data transformation, that capture the machine-independent aspects, to guarantee portability with performance to future processors, with high performance implementations on multicore processors that embed processorspecific optimizations. Our breadth first search graph traversal algorithm demonstrates a capability to process massive graphs with billions of vertices and edges on commodity multicore processors at rates that are competitive with supercomputing results in the recent literature. We also present high performance scalable keyword scanning on streaming data using novel automata compression algorithm, a model of computation based on small software content addressable memories (CAMs) and a unique data layout that forces data re-use and minimizes memory traffic. Using a high-level algorithmic approach to process financial feeds we present a solution that decodes and normalizes option market data at rates an order of magnitude more than the current needs of the market, yet portable and flexible to other feeds in this domain. In this dissertation we discuss in detail algorithm design challenges to process massive-data and present solutions and techniques that we believe can be used and extended to solve future research problems in this domain.

APA, Harvard, Vancouver, ISO, and other styles

36

Vie, Jill-Jênn. "Modèles de tests adaptatifs pour le diagnostic de connaissances dans un cadre d'apprentissage à grande échelle." Thesis, Université Paris-Saclay (ComUE), 2016. http://www.theses.fr/2016SACLC090/document.

Full text

Abstract:

Cette thèse porte sur les tests adaptatifs dans les environnements d’apprentissage. Elle s’inscrit dans les contextes de fouille de données éducatives et d’analytique de l’apprentissage, où l’on s’intéresse à utiliser les données laissées par les apprenants dans des environnements éducatifs pour optimiser l’apprentissage au sens large.L’évaluation par ordinateur permet de stocker les réponses des apprenants facilement, afin de les analyser et d’améliorer les évaluations futures. Dans cette thèse, nous nous intéressons à un certain type de test par ordinateur, les tests adaptatifs. Ceux-ci permettent de poser une question à un apprenant, de traiter sa réponse à la volée, et de choisir la question suivante à lui poser en fonction de ses réponses précédentes. Ce processus réduit le nombre de questions à poser à un apprenant tout en conservant une mesure précise de son niveau. Les tests adaptatifs sont aujourd’hui implémentés pour des tests standardisés tels que le GMAT ou le GRE, administrés à des centaines de milliers d’étudiants. Toutefois, les modèles de tests adaptatifs traditionnels se contentent de noter les apprenants, ce qui est utile pour l’institution qui évalue, mais pas pour leur apprentissage. C’est pourquoi des modèles plus formatifs ont été proposés, permettant de faire un retour plus riche à l’apprenant à l’issue du test pour qu’il puisse comprendre ses lacunes et y remédier. On parle alors de diagnostic adaptatif.Dans cette thèse, nous avons répertorié des modèles de tests adaptatifs issus de différents pans de la littérature. Nous les avons comparés de façon qualitative et quantitative. Nous avons ainsi proposé un protocole expérimental, que nous avons implémenté pour comparer les principaux modèles de tests adaptatifs sur plusieurs jeux de données réelles. Cela nous a amenés à proposer un modèle hybride de diagnostic de connaissances adaptatif, meilleur que les modèles de tests formatifs existants sur tous les jeux de données testés. Enfin, nous avons élaboré une stratégie pour poser plusieursquestions au tout début du test afin de réaliser une meilleure première estimation des connaissances de l’apprenant. Ce système peut être appliqué à la génération automatique de feuilles d’exercices, par exemple sur un cours en ligne ouvert et massif (MOOC)
This thesis studies adaptive tests within learning environments. It falls within educational data mining and learning analytics, where student educational data is processed so as to optimize their learning.Computerized assessments allow us to store and analyze student data easily, in order to provide better tests for future learners. In this thesis, we focus on computerized adaptive testing. Such adaptive tests which can ask a question to the learner, analyze their answer on the fly, and choose the next question to ask accordingly. This process reduces the number of questions to ask to a learner while keeping an accurate measurement of their level. Adaptive tests are today massively used in practice, for example in the GMAT and GRE standardized tests, that are administered to hundreds of thousands of students. Traditionally, models used for adaptive assessment have been mostly summative : they measure or rank effectively examinees, but do not provide any other feedback. Recent advances have focused on formative assessments, that provide more useful feedback for both the learner and the teacher ; hence, they are more useful for improving student learning.In this thesis, we have reviewed adaptive testing models from various research communities. We have compared them qualitatively and quantitatively. Thus, we have proposed an experimental protocol that we have implemented in order to compare the most popular adaptive testing models, on real data. This led us to provide a hybrid model for adaptive cognitive diagnosis, better than existing models for formative assessment on all tried datasets. Finally, we have developed a strategy for asking several questions at the beginning of a test in order to measure the learner more accurately. This system can be applied to the automatic generation of worksheets, for example on a massive online open course (MOOC)

APA, Harvard, Vancouver, ISO, and other styles

37

Khelil, Abdallah. "Gestion et optimisation des données massives issues du Web Combining graph exploration and fragmentation for scalable rdf query processing Should We Be Afraid of Querying Billions of Triples in a Graph-Based Centralized System? EXGRAF : Exploration et Fragmentation de Graphes au Service du Traitement Scalable de Requˆetes RDF." Thesis, Chasseneuil-du-Poitou, Ecole nationale supérieure de mécanique et d'aérotechnique, 2020. http://www.theses.fr/2020ESMA0009.

Full text

Abstract:

Le Big Data représente un défi non seulement pour le monde socio-économique mais aussi pour la recherchescientifique. En effet, comme il a été souligné dans plusieurs articles scientifiques et rapports stratégiques, lesapplications informatiques modernes sont confrontées à de nouveaux problèmes qui sont liés essentiellement austockage et à l’exploitation de données générées par les instruments d’observation et de simulation. La gestion de tellesdonnées représente un véritable goulot d’étranglement qui a pour effet de ralentir la valorisation des différentesdonnées collectées non seulement dans le cadre de programmes scientifiques internationaux mais aussi par desentreprises, ces dernières s'appuyant de plus en plus sur l’analyse de données massives. Une bonne partie de cesdonnées sont publié aujourd’hui sur le WEB. Nous assistons en effet à une évolution du Web classique permettant degérer les documents vers un Web de données qui permet d’offrir des mécanismes d’interrogation des informationssémantiques. Plusieurs modèles de données ont été proposés pour représenter ces informations sur le Web. Le plusimportant est le Resource Description Framework (RDF) qui fournit une représentation des connaissances simple etabstraite pour les ressources sur le Web. Chaque fait du Web sémantique peut être codé avec un triplet RDF. Afin depouvoir explorer et interroger les informations structurées exprimées en RDF, plusieurs langages de requête ont étéproposés au fil des années. En 2008, SPARQL est devenu le langage de recommandation officiel du W3C pourl'interrogation des données RDF. La nécessité de gérer et interroger efficacement les données RDF a conduit audéveloppement de nouveaux systèmes conçus spécialement pour traiter ce format de données. Ces approches peuventêtre catégorisées en étant centralisées qui s’appuient sur une seule machine pour gérer les données RDF et distribuéesqui peuvent combiner plusieurs machines connectées avec un réseau informatique. Certaines de ces approchess’appuient sur un système de gestion de données existant tels que Virtuoso et Jena, d’autres approches sont basées surune approche spécialement conçue pour la gestion des triplets RDF comme GRIN, RDF3X et gStore. Avec l’évolutiondes jeux de données RDF (e.g. DBPedia) et du langage Sparql, la plupart des systèmes sont devenus obsolètes et/ouinefficaces. A titre d’exemple, aucun système centralisé existant n’est en mesure de gérer 1 Milliard de triplets fourniesdans le cadre du benchmark WatDiv. Les systèmes distribués permettraient sous certaines conditions d’améliorer cepoint mais une perte de performances conséquente est induite.Dans cette thèse, nous proposons le système centralisé "RDF_QDAG" qui permet de trouver un bon compromisentre passage à l’échelle et performances. Nous proposons de combiner la fragmentation physique de données etl’exploration du graphe de données. "RDF_QDAG" permet de support plusieurs types de requêtes basées nonseulement sur les motifs basiques de graphes mais aussi qui intègrent des filtres à base d’expressions régulières et aussides fonctions d’agrégation et de tri. "RDF_QDAG" se base sur le modèle d’exécution Volcano, ce qui permet decontrôler la mémoire principale, en évitant tout débordement pour garantir les performances même si la configurationmatérielle est limitée. A notre connaissance, "RDF_QDAG" est le seul système centralisé capable de gérer plusieursmilliards de triplets tout en garantissant de bonnes performances. Nous avons comparé ce système avec d’autressystèmes qui représentent l’état de l’art en matière de gestion de données RDF : une approche relationnelle (Virtuoso),une approche à base de graphes (g-Store), une approche d'indexation intensive (RDF-3X) et une approche MPP(CliqueSquare). "RDF_QDAG" surpasse les systèmes existants lorsqu’il s’agit de garantir à la fois le passage à l’échelleet les performances
Big Data represents a challenge not only for the socio-economic world but also for scientific research. Indeed, as has been pointed out in several scientific articles and strategic reports, modern computer applications are facing new problems and issues that are mainly related to the storage and the exploitation of data generated by modern observation and simulation instruments. The management of such data represents a real bottleneck which has the effect of slowing down the exploitation of the various data collected not only in the framework of international scientific programs but also by companies, the latter relying increasingly on the analysis of large-scale data. Much of this data is published today on the WEB. Indeed, we are witnessing an evolution of the traditional web, designed basically to manage documents, to a web of data that allows to offer mechanisms for querying semantic information. Several data models have been proposed to represent this information on the Web. The most important is the Resource Description Framework (RDF) which provides a simple and abstract representation of knowledge for resources on the Web. Each semantic Web fact can be encoded with an RDF triple. In order to explore and query structured information expressed in RDF, several query languages have been proposed over the years. In 2008,SPARQL became the official W3C Recommendation language for querying RDF data.The need to efficiently manage and query RDF data has led to the development of new systems specifically designed to process this data format. These approaches can be categorized as centralized that rely on a single machine to manage RDF data and distributed that can combine multiple machines connected with a computer network. Some of these approaches are based on an existing data management system such as Virtuoso and Jena, others relies on an approach specifically designed for the management of RDF triples such as GRIN, RDF3X and gStore. With the evolution ofRDF datasets (e.g. DBPedia) and Sparql, most systems have become obsolete and/or inefficient. For example, no one of existing centralized system is able to manage 1 billion triples provided under the WatDiv benchmark. Distributed systems would allow under certain conditions to improve this point but consequently leads a performance degradation. In this Phd thesis, we propose the centralized system "RDF_QDAG" that allows to find a good compromise between scalability and performance. We propose to combine physical data fragmentation and data graph exploration."RDF_QDAG" supports multiple types of queries based not only on basic graph patterns but also that incorporate filters based on regular expressions and aggregation and sorting functions. "RDF_QDAG" relies on the Volcano execution model, which allows controlling the main memory, avoiding any overflow even if the hardware configuration is limited. To the best of our knowledge, "RDF_QDAG" is the only centralized system that good performance when manage several billion triples. We compared this system with other systems that represent the state of the art in RDF data management: a relational approach (Virtuoso), a graph-based approach (g-Store), an intensive indexing approach (RDF-3X) and two parallel approaches (CliqueSquare and g-Store-D). "RDF_QDAG" surpasses existing systems when it comes to ensuring both scalability and performance

APA, Harvard, Vancouver, ISO, and other styles

38

Kirchgessner, Martin. "Fouille et classement d'ensembles fermés dans des données transactionnelles de grande échelle." Thesis, Université Grenoble Alpes (ComUE), 2016. http://www.theses.fr/2016GREAM060/document.

Full text

Abstract:

Les algorithmes actuels pour la fouille d’ensembles fréquents sont dépassés par l’augmentation des volumes de données. Dans cette thèse nous nous intéressons plus particulièrement aux données transactionnelles (des collections d’ensembles d’objets, par exemple des tickets de caisse) qui contiennent au moins un million de transactions portant sur au moins des centaines de milliers d’objets. Les jeux de données de cette taille suivent généralement une distribution dite en "longue traine": alors que quelques objets sont très fréquents, la plupart sont rares. Ces distributions sont le plus souvent tronquées par les algorithmes de fouille d’ensembles fréquents, dont les résultats ne portent que sur une infime partie des objets disponibles (les plus fréquents). Les méthodes existantes ne permettent donc pas de découvrir des associations concises et pertinentes au sein d’un grand jeu de données. Nous proposons donc une nouvelle sémantique, plus intuitive pour l’analyste: parcourir les associations par objet, au plus une centaine à la fois, et ce pour chaque objet présent dans les données.Afin de parvenir à couvrir tous les objets, notre première contribution consiste à définir la fouille centrée sur les objets. Cela consiste à calculer, pour chaque objet trouvé dans les données, les k ensembles d’objets les plus fréquents qui le contiennent. Nous présentons un algorithme effectuant ce calcul, TopPI. Nous montrons que TopPI calcule efficacement des résultats intéressants sur nos jeux de données. Il est plus performant que des solutions naives ou des émulations reposant sur des algorithms existants, aussi bien en termes de rapidité que de complétude des résultats. Nous décrivons et expérimentons deux versions parallèles de TopPI (l’une sur des machines multi-coeurs, l’autre sur des grappes Hadoop) qui permettent d’accélerer le calcul à grande échelle.Notre seconde contribution est CAPA, un système permettant d’étudier quelle mesure de qualité des règles d’association serait la plus appropriée pour trier nos résultats. Cela s’applique aussi bien aux résultats issus de TopPI que de jLCM, notre implémentation d’un algorithme récent de fouille d’ensembles fréquents fermés (LCM). Notre étude quantitative montre que les 39 mesures que nous comparons peuvent être regroupées en 5 familles, d’après la similarité des classements de règles qu’elles produisent. Nous invitons aussi des experts en marketing à participer à une étude qualitative, afin de déterminer laquelle des 5 familles que nous proposons met en avant les associations d’objets les plus pertinentes dans leur domaine.Notre collaboration avec Intermarché, partenaire industriel dans le cadre du projet Datalyse, nous permet de présenter des expériences complètes et portant sur des données réelles issues de supermarchés dans toute la France. Nous décrivons un flux d’analyse complet, à même de répondre à cette application. Nous présentons également des expériences portant sur des données issues d’Internet; grâce à la généricité du modèle des ensembles d’objets, nos contributions peuvent s’appliquer dans d’autres domaines.Nos contributions permettent donc aux analystes de découvrir des associations d’objets au milieu de grandes masses de données. Nos travaux ouvrent aussi la voie vers la fouille d’associations interactive à large échelle, afin d’analyser des données hautement dynamiques ou de réduire la portion du fichier à analyser à celle qui intéresse le plus l’analyste
The recent increase of data volumes raises new challenges for itemset mining algorithms. In this thesis, we focus on transactional datasets (collections of items sets, for example supermarket tickets) containing at least a million transactions over hundreds of thousands items. These datasets usually follow a "long tail" distribution: a few items are very frequent, and most items appear rarely. Such distributions are often truncated by existing itemset mining algorithms, whose results concern only a very small portion of the available items (the most frequents, usually). Thus, existing methods fail to concisely provide relevant insights on large datasets. We therefore introduce a new semantics which is more intuitive for the analyst: browsing associations per item, for any item, and less than a hundred associations at once.To address the items' coverage challenge, our first contribution is the item-centric mining problem. It consists in computing, for each item in the dataset, the k most frequent closed itemsets containing this item. We present an algorithm to solve it, TopPI. We show that TopPI computes efficiently interesting results over our datasets, outperforming simpler solutions or emulations based on existing algorithms, both in terms of run-time and result completeness. We also show and empirically validate how TopPI can be parallelized, on multi-core machines and on Hadoop clusters, in order to speed-up computation on large scale datasets.Our second contribution is CAPA, a framework allowing us to study which existing measures of association rules' quality are relevant to rank results. This concerns results obtained from TopPI or from jLCM, our implementation of a state-of-the-art frequent closed itemsets mining algorithm (LCM). Our quantitative study shows that the 39 quality measures we compare can be grouped into 5 families, based on the similarity of the rankings they produce. We also involve marketing experts in a qualitative study, in order to discover which of the 5 families we propose highlights the most interesting associations for their domain.Our close collaboration with Intermarché, one of our industrial partners in the Datalyse project, allows us to show extensive experiments on real, nation-wide supermarket data. We present a complete analytics workflow addressing this use case. We also experiment on Web data. Our contributions can be relevant in various other fields, thanks to the genericity of transactional datasets.Altogether our contributions allow analysts to discover associations of interest in modern datasets. We pave the way for a more reactive discovery of items' associations in large-scale datasets, whether on highly dynamic data or for interactive exploration systems

APA, Harvard, Vancouver, ISO, and other styles

39

Woltering, Matthias [Verfasser]. "Factor Graph-based Receivers for Multi-Carrier Transmission in Two-Way Relaying and Massive Machine Type Communications / Matthias Woltering." Düren : Shaker, 2019. http://d-nb.info/1202218644/34.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Jaffré, Marc-Olivier. "Connaissance et optimisation de la prise en charge des patients : la science des réseaux appliquée aux parcours de soins." Thesis, Compiègne, 2018. http://www.theses.fr/2018COMP2445/document.

Full text

Abstract:

En France, la nécessaire rationalisation des moyens alloués aux hôpitaux a abouti à une concentration des ressources et une augmentation de la complexité des plateaux techniques. Leur pilotage et leur répartition territoriale s’avèrent d’autant plus difficile, soulevant ainsi la problématique de l’optimisation des systèmes de soins. L’utilisation des données massives produites pas ces systèmes pourrait constituer une nouvelle approche en matière d’analyse et d’aide à la décision. Méthode : A partir d’une réflexion sur la notion de performance, différentes approches d’optimisation préexistantes sont d’abord mis en évidence. Le bloc opératoire a été choisi en tant que terrain expérimental. Suit une analyse sur une fusion d’établissements en tant qu’exemple d’une approche d’optimisation par massification.Ces deux étapes permettent de défendre une approche alternative qui associe l’usage de données massives, la science des réseaux et la visualisation des données sous forme cartographique. Deux sets de séjours en chirurgie orthopédique sur la région ex-Midi-Pyrénées sont utilisés. L’enchainement des séjours de soins est considéré en tant en réseau de données. L’ensemble est projeté dans un environnement visuel développé en JavaScript et permettant une fouille dynamique du graphe. Résultats : La possibilité de visualiser des parcours de santé sous forme de graphes NŒUDS-LIENS est démontrée. Les graphes apportent une perception supplémentaire sur les enchainements de séjours et les redondances des parcours. Le caractère dynamique des graphes permet en outre leur fouille. L’approche visuelle subjective est complétée par une série de mesures objectives issues de la science des réseaux. Les plateaux techniques de soins produisent des données massives utiles à leur analyse et potentiellement à leur optimisation. La visualisation graphique de ces données associées à un cadre d’analyse tel que la science des réseaux donne des premiers indicateurs positifs avec notamment la mise en évidence de motifs redondants. La poursuite d’expérimentations à plus large échelle est requise pour valider, renforcer et diffuser ces observations et cette méthode
In France, the streamlining of means assigned hospitals result in concentration of resources ana growing complexily of heallhcare facilities. Piloting and planning (them turn out to be all the more difficult, thus leading of optimjzation problems. The use of massive data produced by these systems in association with network science an alternative approach for analyzing and improving decision-making support jn healthcare. Method : Various preexisting optimisation are first highblighted based on observations in operating theaters chosen as experirnentai sites. An analysis of merger of two hospitlas also follows as an example of an optimization method by massification. These two steps make it possible to defend an alternative approach that combines the use of big data science of networks data visualization techniques. Two sets of patient data in orthopedic surgery in the ex-Midi-Pyrénées region in France are used to create a network of all sequences of care. The whole is displayed in a visual environment developed in JavaScript allowing a dynamic mining of the graph. Results: Visualizing healthcare sequences in the form of nodes and links graphs has been sel out. The graphs provide an additional perception of' the redundancies of he healthcare pathways. The dynamic character of the graphs also allows their direct rnining. The initial visual approach is supplernented by a series of objcctive measures from the science of networks. Conciusion: Healthcare facilities produce massive data valuable for their analysis and optimization. Data visualizalion together with a framework such as network science gives prelimiaary encouraging indicators uncovering redondant healthcare pathway patterns. Furthev experimentations with various and larger sets of data is required to validate and strengthen these observations and methods

APA, Harvard, Vancouver, ISO, and other styles

41

Silva, Flamys Lena do Nascimento 1979. "Aplicação da espectrometria de massas na avaliação da composição química de vinhos e uvas." [s.n.], 2013. http://repositorio.unicamp.br/jspui/handle/REPOSIP/248698.

Full text

Abstract:

Orientador: Marcos Nogueira Eberlin
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Química
Made available in DSpace on 2018-08-22T17:49:00Z (GMT). No. of bitstreams: 1 Silva_FlamysLenadoNascimento_D.pdf: 3948483 bytes, checksum: d08c9b4a732a432656e3795bc2d362dc (MD5) Previous issue date: 2013
Resumo: As variedades de uvas do gênero Vitis vinífera, incluindo a uva Syrah, são amplamente utilizadas na vinificação. O híbrido (Máximo-IAC 138-22), obtida do cruzamento entre Syrah e Seibel 11342 tem mostrado grande capacidade de adaptação ao clima de São Paulo e, aparentemente, produz um vinho de boa qualidade. A primeira parte deste estudo consistiu em comparar a composição volátil no headspace do vinho tinto paulista com outros vinhos originados da casta fina Syrah de diferentes regiões do mundo. Para isso foi empregada a técnica de microextração em fase sólida (SPME) com a cromatografia em fase gasosa acoplada à espectrometria de massas (GC-MS). Na segunda parte foi estudado o perfil fenólico de vinhos empregando a técnica de ionização por eletrospray (ESI) acoplada com a espectrometria de massas de ressonância ciclotrônica de íons com transformada de Fourier (FT-ICR MS) que permitiu a detecção de milhares de compostos polares no vinho sem separação cromatográfica e simples preparo de amostra. Constatou-se que o vinho paulista possui um perfil fenólico similar aos outros vinhos comerciais da uva Syrah. No terceiro e quarto estudos empregou-se a técnica ESI-MS por inserção direta para quantificar os ácidos orgânicos em vinho e em uva. Apesar de o vinho constituir uma matriz complexa, a técnica ESI-MS por inserção direta permitiu quantificar os compostos polares majoritários tais como ácido málico, ácido tartárico e ácido cítrico. Nas uvas Vitis vinífera, Vitis labrusca e híbridos a análise de componentes principais (PCA) mostrou clara distinção entre vinhos de uvas diferentes e o agrupamento do vinho paulista com os vinhos da uva Syrah. O método ESI-MS por inserção direta está sendo proposto pela primeira vez para quantificação de ácidos em vinhos e uvas. O método aqui desenvolvido foi validado segundo as normas do Instituto Nacional de Metrologia, Qualidade e Tecnologia (INMETRO)
Abstract: Varieties of grapes from the Vitis vinifera group incluind the Syrah grape are the most widely used for winemaking. A hybrid grape (Maximum-IAC 138-22) obtained by crossing Syrah and Seibel 11342 grapes has shown great adaptability in São Paulo State, producing apparently a high quality wine. This part first has compared the headspace aroma volatile composition of wine made from the Maximum IAC 138-22 grape with wines made from Syrah varietals originated from different regions of the world. Using static solid-phase microextration (SPME) followed by gas chromatography-mass spectrometry (GC-MS) analysis, main volatile compounds were identifield. Hierarchical clustering analysis (HCA) showed that the wine from the hybrid grape Maximum 138-22 has volatile aroma composition very similar to most high quality Syrah grape wines studied. In the second part the phenolic profile wine using the technique of electrospray ionization (ESI) coupled with mass spectrometry íon cyclotron resonance Fourier transform (FT-ICR MS) that allows detection of thousands of polar compounds in wine without chromatographic separation and simple sample preparation. Was found that the wine paulista has a profile similar phenolic other commercial wines from Syrah grapes. The ESI-MS technique for direct insertion allows us to obtain qualitative and quantitative results without chromatographic separation of wine. In the third and fourth studies employed the technique ESI-MS by direct insertion for quantifying organics acids in wine and grapes. As the wine is a complex matrix, pre concentration and filtration ESI-MS for direct insertion quantify the major polar compounds such as malic acid, tartaric acid and citric acid. In Vitis vinifera grape, Vitis labrusca and hybrid the principal component analysis (PCA) showed a clear distinction between wines from different grapes and wine group in São Paulo with wines from Syrah grapes. The ESI-MS method for direct insertion is first proposed for quantification of acids in wines and grapes. The method ESI-MS by direct insertion is first proposed for quantification acid in wines and grapes. The method developed here was validated according to the standards of the National Health Surveillance Agency and National Institute of Metrology, Quality and Technology (INMETRO)
Doutorado
Quimica Analitica
Doutora em Ciências

APA, Harvard, Vancouver, ISO, and other styles

42

Qiao, Wenbao. "GPU component-based neighborhood search for Euclidean graph minimization problems." Thesis, Bourgogne Franche-Comté, 2018. http://www.theses.fr/2018UBFCA020.

Full text

Abstract:

Dans cette thèse, nous proposons des solutions parrallèles basées sur le systèmes actuel GPU (graphics processing unit) pour deux problèmes de minimisation de graphe Euclidien, à savoir le problème de forêt/arbre couvrant minimum Euclidien (EMSF / EMST) et le problème du voyageur commerce (TSP). Les solutions proposées résolvent également aussi le problème d'une paire bichromatique la plus proche (BCP), et suivent la technique de ``contrôle décentralisé, du parallélisme des données et des mémoires partagées par GPU".Nous proposons une technique de recherche dans le voisinage le plus proche de dimension K Euclidienne basée sur les approches classiques de NNS d’Elias qui divisent l’espace Euclidien en cellules congruentes et ne se chevauchant pas, où la taille des points de chaque cellule est délimitée. Nous proposons aussi une technique d'élagage pour obtenir le NNS à base de composants afin de trouver le point de sortie le plus proche de l'ensemble de points de requête de Q dans la complexité temporelle linéaire séquentielle lorsque les données sont uniformément réparties. Ces techniques sont utilisées conjointement avec deux GPU algorithmes proposés pour arbre traversement, à savoir la recherche en largeur bidirectionnelle GPU et la liste chaînée dynamique distribuée, afin d'adresser le BCP. Basé sur la solution BCP, un algorithme parallèle Divide and Conquer est implémenté pour construire EMSF et EMST totalement côté GPU. Le TSP est adressé avec différents algorithmes de recherche locaux parallèles 2-opt, dans lesquels nous proposons une méthodologie ``évaluation multiple K-opt, mouvements multiples K-opt" afin d’exécuter simultanément, sans interférence, des processus massifs 2-/3-opt mouvements qui se retrouvent globalement sur le même circuit TSP pour de nombreux bords. Cette méthodologie est expliquée en détail pour montrer comment nous obtenons un calcul haute performance à la fois du côté du GPU et CPU. Nous testons les solutions proposées et rapportons des résultats de comparaison expérimentale par rapport aux algorithmes de pointe
In this thesis, we propose parallel solutions based on current graphics processing unit (GPU) system for two Euclidean graph minimization problems, namely the Euclidean minimum spanning forest/tree (EMSF/EMST) and the travelling salesman problem (TSP). The proposed solutions also solve the bichromatic closest pair (BCP) problem, and follow technique of ``decentralized control, data parallelism, GPU shared memories".We propose a Euclidean K-dimensional nearest neighbourhood search (NNS) technique based on classical Elias' NNS approaches that divide the Euclidean space into congruent and non-overlapping cells where size of points in each cell is bounded. We propose a pruning technique to obtain component-based NNS to find a query point set Q's closest outgoing point within sequential linear time complexity when the data is uniformly distributed. These techniques are used together with two proposed GPU tree traversal algorithms, namely the GPU two-direction Breadth-first search and distributed dynamic linked list, to address the BCP. Based on the BCP solution, a divide and conquer parallel algorithm is implemented for building EMSF and EMST totally on GPU side. The TSP is addressed with different parallel 2-opt local search algorithms, in which we propose a ``multiple K-opt evaluation, multiple K-opt moves" methodology in order to simultaneously execute, without interference, massive 2-/3-opt moves that are globally found on the same TSP tour for many edges. This methodology is explained in details to show how we obtain high performance computing both on GPU and CPU side. We test the proposed solutions and report experimental comparison results against the state-of-the-art algorithms

APA, Harvard, Vancouver, ISO, and other styles

43

Ayed, Rihab. "Recherche d’information agrégative dans des bases de graphes distribuées." Thesis, Lyon, 2019. http://www.theses.fr/2019LYSE1305.

Full text

Abstract:

Le sujet de cette thèse s’inscrit dans le cadre général de la Recherche d’Information et la gestion des données massives et distribuées. Notre problématique concerne l’évaluation et l’optimisation de requêtes agrégatives (Aggregated Search). La Recherche d’Information Agrégative est un nouveau paradigme permettant l’accès à l’information massivement distribuée. Elle a pour but de retourner à l’utilisateur d’un système de recherche d’information des objets résultats qui sont riches et porteurs de connaissances. Ces objets n’existent pas en tant que tels dans les sources. Ils sont construits par assemblage (ou configuration ou agrégation) de fragments issus de diffèrentes sources. Les sources peuvent être non spécifiées dans l’expression de la requête mais découvertes dynamiquement lors de la recherche. Nous nous intéressons particulièrement à l’exploitation des dépendances de données pour optimiser les accès aux sources distribuées. Dans ce cadre, nous proposons une approche pour l’un des sous processus de systèmes de RIA, principalement le processus d’indexation/organisation des documents. Nous considérons dans cette thèse, les systèmes de recherche d’information orientés graphes (graphes RDF). Utilisant les relations dans les graphes, notre travail s’inscrit dans le cadre de la recherche d’information agrégative relationnelle (Relational Aggregated Search) où les relations sont exploitées pour agréger des fragments d’information. Nous proposons d’optimiser l’accès aux sources d’information dans un système de recherche d’information agrégative. Ces sources contiennent des fragments d’information répondant partiellement à la requête. L’objectif est de minimiser le nombre de sources interrogées pour chaque fragment de la requête, ainsi que de maximiser les opérations d’agrégations de fragments dans une même source. Nous proposons d’effectuer cela en réorganisant la/les base(s) de graphes dans plusieurs clusters d’information dédiés aux requêtes agrégatives. Ces clusters sont obtenus à partir d’une approche de clustering sémantique ou structurel des prédicats des graphes RDF. Pour le clustering structurel, nous utilisons les algorithmes d’extraction de sous-graphes fréquents et dans ce cadre nous élaborons une étude comparative des performances de ces algorithmes. Pour le clustering sémantique, nous utilisons les métadonnées descriptives des prédicats dont nous appliquons des outils de similarité textuelle sémantique. Nous définissons une approche de décomposition de requêtes basée essentiellement sur le clustering choisi
In this research, we are interested in investigating issues related to query evaluation and optimization in the framework of aggregated search. Aggregated search is a new paradigm to access massively distributed information. It aims to produce answers to queries by combining fragments of information from different sources. The queries search for objects (documents) that do not exist as such in the targeted sources, but are built from fragments extracted from the different sources. The sources might not be specified in the query expression, they are dynamically discovered at runtime. In our work, we consider data dependencies to propose a framework for optimizing query evaluation over distributed graph-oriented data sources. For this purpose, we propose an approach for the document indexing/orgranizing process of aggregated search systems. We consider information retrieval systems that are graph oriented (RDF graphs). Using graph relationships, our work is within relational aggregated search where relationships are used to aggregate fragments of information. Our goal is to optimize the access to source of information in a aggregated search system. These sources contain fragments of information that are relevant partially for the query. We aim at minimizing the number of sources to ask, also at maximizing the aggregation operations within a same source. For this, we propose to reorganize the graph database(s) in partitions, dedicated to aggregated queries. We use a semantic or strucutral clustering of RDF predicates. For structural clustering, we propose to use frequent subgraph mining algorithms, we performed for this, a comparative study of their performances. For semantic clustering, we use the descriptive metadata of RDF predicates and apply semantic textual similarity methods to calculate their relatedness. Following the clustering, we define query decomposing rules based on the semantic/structural aspects of RDF predicates

APA, Harvard, Vancouver, ISO, and other styles

44

Silva, Neto Otilio Paulo da. "Detecção automática de massas em imagens mamográficas usando particle swarm optimization (PSO) e índice de diversidade funcional." Universidade Federal do Maranhão, 2016. http://tedebc.ufma.br:8080/jspui/handle/tede/298.

Full text

Abstract:

Made available in DSpace on 2016-08-17T14:52:40Z (GMT). No. of bitstreams: 1 Dissertacao-OtilioPauloSilva.pdf: 2236988 bytes, checksum: e67439b623fd83b01f7bcce0020365fb (MD5) Previous issue date: 2016-03-04
Breast cancer is now set on the world stage as the most common among women and the second biggest killer. It is known that diagnosed early, the chance of cure is quite significant, on the other hand, almost late discovery leads to death. Mammography is the most common test that allows early detection of cancer, this procedure can show injury in the early stages also contribute to the discovery and diagnosis of breast lesions. Systems computer aided, have been shown to be very important tools in aid to specialists in diagnosing injuries. This paper proposes a computational methodology to assist in the discovery of mass in dense and nondense breasts. This paper proposes a computational methodology to assist in the discovery of mass in dense and non-dense breasts. Divided into 6 stages, this methodology begins with the acquisition of the acquired breast image Digital Database for Screening Mammography (DDSM). Then the second phase is done preprocessing to eliminate and enhance the image structures. In the third phase is executed targeting with the Particle Swarm Optimization (PSO) to find regions of interest (ROIs) candidates for mass. The fourth stage is reduction of false positives, which is divided into two parts, reduction by distance and clustering graph, both with the aim of removing unwanted ROIs. In the fifth stage are extracted texture features using the functional diversity indicia (FD). Finally, in the sixth phase, the classifier uses support vector machine (SVM) to validate the proposed methodology. The best values found for non-dense breasts, resulted in sensitivity of 96.13%, specificity of 91.17%, accuracy of 93.52%, the taxe of false positives per image 0.64 and acurva free-response receiver operating characteristic (FROC) with 0.98. The best finds for dense breasts hurt with the sensitivity of 97.52%, specificity of 92.28%, accuracy of 94.82% a false positive rate of 0.38 per image and FROC curve 0.99. The best finds with all the dense and non dense breasts Showed 95.36% sensitivity, 89.00% specificity, 92.00% accuracy, 0.75 the rate of false positives per image and 0, 98 FROC curve.
O câncer de mama hoje é configurado no senário mundial como o mais comum entre as mulheres e o segundo que mais mata. Sabe-se que diagnosticado precocemente, a chance de cura é bem significativa, por outro lado, a descoberta tardia praticamente leva a morte. A mamografia é o exame mais comum que permite a descoberta precoce do câncer, esse procedimento consegue mostrar lesões nas fases iniciais, além de contribuir para a descoberta e o diagnóstico de lesões na mama. Sistemas auxiliados por computador, têm-se mostrado ferramentas importantíssimas, no auxilio a especialistas em diagnosticar lesões. Este trabalho propõe uma metodologia computacional para auxiliar na descoberta de massas em mamas densas e não densas. Dividida em 6 fases, esta metodologia se inicia com a aquisição da imagem da mama adquirida da Digital Database for Screening Mammography (DDSM). Em seguida, na segunda fase é feito o pré-processamento para eliminar e realçar as estruturas da imagem. Na terceira fase executa-se a segmentação com o Particle Swarm Optimization (PSO) para encontrar as regiões de interesse (ROIs) candidatas a massa. A quarta fase é a redução de falsos positivos, que se subdivide em duas partes, sendo a redução pela distância e o graph clustering, ambos com o objetivo de remover ROIs indesejadas. Na quinta fase são extraídas as características de textura utilizando os índices de diversidade funcional (FD). Por fim, na sexta fase, utiliza-se o classificador máquina de vetores de suporte (SVM) para validar a metodologia proposta. Os melhores valores achados para as mamas não densas, resultaram na sensibilidade de 96,13%, especificidade de 91,17%, acurácia de 93,52%, a taxe de falsos positivos por imagem de 0,64 e a acurva Free-response Receiver Operating Characteristic (FROC) com 0,98. Os melhores achados para as mamas densas firam com a sensibilidade de 97,52%, especificidade de 92,28%, acurácia de 94,82%, uma taxa de falsos positivos por imagem de 0,38 e a curva FROC de 0,99. Os melhores achados com todas as mamas densas e não densas, apresentaram 95,36% de sensibilidade, 89,00% de especificidade, 92,00% de acurácia, 0,75 a taxa de falsos positivos por imagem e 0,98 a curva FROC.

APA, Harvard, Vancouver, ISO, and other styles

45

Moscu, Mircea. "Inférence distribuée de topologie de graphe à partir de flots de données." Thesis, Université Côte d'Azur, 2020. http://www.theses.fr/2020COAZ4081.

Full text

Abstract:

La deuxième décennie du millénaire actuel peut être résumée en une courte phrase : l'essor des données. Le nombre de sources de données s'est multiplié : du streaming audio-vidéo aux réseaux sociaux et à l'Internet des Objets, en passant par les montres intelligentes, les équipements industriels et les véhicules personnels, pour n'en citer que quelques-unes. Le plus souvent, ces sources forment des réseaux afin d'échanger des informations. En conséquence directe, le domaine du Traitement de Signal sur Graphe a prospéré et a évolué. Son but : traiter et donner un sens à tout le déluge de données environnant. Dans ce contexte, le but principal de cette thèse est de développer des méthodes et des algorithmes capables d'utiliser des flots de données, de manière distribuée, afin d'inférer les réseaux sous-jacents qui relient ces flots. Ensuite, ces topologies de réseau estimées peuvent être utilisées avec des outils développés pour le Traitement de Signal sur Graphe afin de traiter et d'analyser les données supportées par des graphes. Après une brève introduction suivie d'exemples motivants, nous développons et proposons d'abord un algorithme en ligne, distribué et adaptatif pour l'inférence de topologies de graphes pour les flots de données qui sont linéairement dépendants. Une analyse de la méthode s'ensuit, afin d'établir des relations entre les performances et les paramètres nécessaires à l'algorithme. Nous menons ensuite une série d'expériences afin de valider l'analyse et de comparer ses performances avec celles d'une autre méthode proposée dans la littérature. La contribution suivante est un algorithme doté des mêmes capacités en ligne, distribuées et adaptatives, mais adapté à l'inférence de liens entre des données qui interagissent de manière non-linéaire. À ce titre, nous proposons un modèle additif simple mais efficace qui utilise l'usine du noyau reproduisant afin de modéliser lesdites non-linéarités. Les résultats de son analyse sont convaincants, tandis que les expériences menées sur des données biomédicales donnent des réseaux estimés qui présentent un comportement prédit par la littérature médicale. Enfin, une troisième proposition d'algorithme est faite, qui vise à améliorer le modèle non-linéaire en lui permettant d'échapper aux contraintes induites par l'additivité. Ainsi, le nouveau modèle proposé est aussi général que possible, et utilise une manière naturelle et intuitive d'imposer la parcimonie des liens, basée sur le concept de dérivés partiels. Nous analysons également l'algorithme proposé, afin d'établir les conditions de stabilité et les relations entre ses paramètres et ses performances. Une série d'expériences est menée, montrant comment le modèle général est capable de mieux saisir les liens non-linéaires entre les données, tandis que les réseaux estimés se comportent de manière cohérente avec les estimations précédentes
The second decade of the current millennium can be summarized in one short phrase: the advent of data. There has been a surge in the number of data sources: from audio-video streaming, social networks and the Internet of Things, to smartwatches, industrial equipment and personal vehicles, just to name a few. More often than not, these sources form networks in order to exchange information. As a direct consequence, the field of Graph Signal Processing has been thriving and evolving. Its aim: process and make sense of all the surrounding data deluge.In this context, the main goal of this thesis is developing methods and algorithms capable of using data streams, in a distributed fashion, in order to infer the underlying networks that link these streams. Then, these estimated network topologies can be used with tools developed for Graph Signal Processing in order to process and analyze data supported by graphs. After a brief introduction followed by motivating examples, we first develop and propose an online, distributed and adaptive algorithm for graph topology inference for data streams which are linearly dependent. An analysis of the method ensues, in order to establish relations between performance and the input parameters of the algorithm. We then run a set of experiments in order to validate the analysis, as well as compare its performance with that of another proposed method of the literature.The next contribution is in the shape of an algorithm endowed with the same online, distributed and adaptive capacities, but adapted to inferring links between data that interact non-linearly. As such, we propose a simple yet effective additive model which makes use of the reproducing kernel machinery in order to model said nonlinearities. The results if its analysis are convincing, while experiments ran on biomedical data yield estimated networks which exhibit behavior predicted by medical literature.Finally, a third algorithm proposition is made, which aims to improve the nonlinear model by allowing it to escape the constraints induced by additivity. As such, the newly proposed model is as general as possible, and makes use of a natural and intuitive manner of imposing link sparsity, based on the concept of partial derivatives. We analyze this proposed algorithm as well, in order to establish stability conditions and relations between its parameters and its performance. A set of experiments are ran, showcasing how the general model is able to better capture nonlinear links in the data, while the estimated networks behave coherently with previous estimates

APA, Harvard, Vancouver, ISO, and other styles

46

Fonseca, Andresa Maíra da. "Cianobactérias e cianotoxinas em áreas recreacionais do Reservatório de Salto Grande, Americana - SP." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/11/11138/tde-12082014-083903/.

Full text

Abstract:

As cianobactérias produzem substâncias tóxicas que são conhecidas como cianotoxinas. Inúmeros casos de intoxicações em humanos e animais têm sido reportados nos mais diversos países. Várias cianobactérias tóxicas são planctônicas e desenvolvem-se em ambientes de água doce formando florações intensas sob condições favoráveis. Florações de cianobactérias têm sido observadas durante todo o ano no reservatório Salto Grande (Americana, SP) que possui intenso uso recreacional, além de servir para abastecimento público de água, pesca e irrigação de culturas. Portanto, avaliar a comunidade de cianobactérias e identificar a presença de genes de cianotoxinas, bem como detectar a produção de toxinas em florações do reservatório de Salto Grande é de fundamental importância para os órgãos de saúde pública para permitir a utilização segura desses corpos d\'água. Neste estudo, três amostras de água com florações de cianobactérias foram analisadas, as quais foram coletadas em diferentes períodos, em dois locais com intenso uso recreacional. As investigações sob microscópio óptico das amostras preservadas com solução de lugol identificaram quinze gêneros cianobacterianos, sendo dois deles até então desconhecidos para o local (Plantothrix e Komvophorum). As contagens de células usando a técnica de Utermöl realizadas para duas das amostras de água mostraram valores que excedem os recomendados pela Portaria Nº 2914 do Ministério da Saúde, a qual estabelece análises e coletas semanais da água acima de 20.000 células/mL. O potencial genético para produção das toxinas cilindrospermopsina, saxitoxina e microcistina foi avaliado a partir da extração do DNA genômico total das amostras ambientais e observou-se amplificação por PCR dos genes cyrJ, sxtA, sxtI, mcyE e mcyG. Os produtos da PCR foram sequenciados e as análises filogenéticas das sequências de aminoácidos mostraram que elas se agruparam com sequências homólogas de cianobactérias conhecidas como produtoras das respectivas toxinas. No entanto, as análises químicas de LC-MS/MS das amostras ambientais buscando as três referidas toxinas detectaram a presença somente de microcistina. As variantes de microcistinas encontradas foram as MC-LR e MC-RR. Os resultados deste estudo contribuem para o aumento de informações sobre o reservatório Salto Grande, e mais uma vez alertam para a preocupante situação deste reservatório em relação à saúde pública.
Cyanobacteria produce toxic substances which are known as cyanotoxins. Numerous cases of poisoning in humans and animals have been reported in several countries. Several toxic cyanobacteria are planktonic and develop in freshwater environments forming intense blooms under favorable conditions. Cyanobacterial blooms have been observed throughout the year in the Salto Grande reservoir (Americana, SP) that has intense recreational use, besides serves to public water supply, fisheries and crop irrigation. Therefore, evaluate cyanobacterial community and identify the presence of cyanotoxin genes as well as assess the production of toxins in blooms from the Salto Grande reservoir is of fundamental importance to public health agencies to allow safe uses of these water bodies. In this study, three water samples with cyanobacterial bloom were analyzed, which were collected at different periods, in two locations with intense recreational use. Investigations under optical microscope of the samples preserved with Lugol\'s iodine solution identified fifteen cyanobacterial genera, being two of them hitherto unknown to the location (Plantothrix and Komvophorum). Cell counts using the Utermöl technique performed for two water samples showed values exceeding those recommended by the Regulation Nº 2.914 of the Brazilian Ministry of Health, which establish weekly analyzes and sampling of water above 20,000 cells/mL. The genetic potential for production of the toxins cylindrospermopsin, saxitoxin and microcystin was evaluated using total genomic DNA from the environment samples and it was observed PCR amplification of the genes cyrJ, sxtA, sxtI, mcyE and mcyG. The PCR products were sequenced and phylogenetic analyses of amino acid sequences showed that they grouped with homologous sequences of known cyanobacterial producers of the respective toxins. However, the chemical analyzes of LC-MS/MS of the environmental samples searching for the three referred toxins detected only the presence of microcystin. The microcystin variants found were MC-LR and MC-RR. The results of this study contribute to the increase of information on the Salto Grande reservoir, and once again warming to the alarming situation of this reservoir related to public health.

APA, Harvard, Vancouver, ISO, and other styles

47

Moutard, Thibaud. "Redshifts photométriques et paramètres physiques des galaxies dans les sondages à grande échelle : contraintes sur l'évolution des galaxies massives." Thesis, Aix-Marseille, 2015. http://www.theses.fr/2015AIXM4782.

Full text

Abstract:

Cette thèse présente la mesure des redshifts photométriques et des paramètres physiques dans le cadre des sondages de galaxies à grande échelle, ainsi que la contrainte qui peut en être extraite sur l'évolution des galaxies. Je montre notamment dans cette thèse dans quelle mesure la calibration photométrique affecte la précision des redshifts photométriques, afin de contraindre la stratégie photométrique à développer pour la mission Euclid.Afin de prendre en compte les problèmes inhérents à l'observation, les analyses ont été effectuée sur la base de données observées dont la configuration est proche de celle qui est attendue pour Euclid. Ces données combinent de nouvelles observations en proche-infrarouges conduites pour couvrir le sondage spectroscopique VIPERS et la photométrie du CFHTLS. Sur la base des conclusions tirées de cette analyse, j'ai produit le nouveau catalogue photométrique de VIPERS, ainsi que le catalogue de redshifts photométriques associé. J'ai finalement utilisée la même photométrie pour dériver les paramètres physiques d'environ 760 000 galaxies, réparties sur plus de 22 degrés carrés à une magnitude limite Ks(AB) < 22. J'ai ainsi pu étudier l'évolution de la fonction de masse stellaire entre les redshifts z = 0.2 et z = 1.5. Ceci a permis de montrer que les galaxies dont la masse stellaire est d'environ log(M/Msol) = 10.66 voient généralement leur formation stellaire stoppée en 2 à 4 milliards d'années, alors que les galaxies de faible masse (log(M/Msol) < 9.5) ne formant plus d'étoiles ont vu leur formation stellaire être arrêtée 5 à 10 fois plus rapidement (en environ 0.4 milliard d'années)
This thesis presents the measurement of the photometric redshifts and physical parameters in the framework of large scale surveys, and their constraint on galaxy evolution. The photometric redshift measurement allows us to study the entire photometric sample. For this reason, the weak lensing signal measurement used in the Euclid mission as a primary cosmological probe will rely on photometric redshift measurements. However, the method is strongly affected by the quality of the photometry. In particular, I show in this thesis how the photometric calibration impacts the photometric redshift precison, in order to constrain the photometric strategy to use in the Euclid mission.Aiming to take into account for observationnal problems, the analysis is done with observationnal data whose photometric configuration is close to the expected Euclid one. These data combine new near-infrared observations conduected to cover the VIPERS spectroscopic survey and the CFHTLS photometry.Using the conclusions of this analysis, I have producted the new photometric catalogue for VIPERS and the associated photometric redshift calalogue.Finally, I used the same photometry to compute the stellar masses of 760,000 galaxies covering 22 square degrees at the limiting magnitude Ks(AB) < 22. This enabled me to study the evolution of the stellar mass function between redshifts z= 0.2 and z = 1.5. We have then shown that the star formation of galaxies with stellar masses around log(M/Msol) = 10.66 is stopped in 2-4 Gyr, while in quiescent low-mass (log(M/Msol) < 9.5) galaxies, the star formation has been stopped 5-10 times faster (approximatelly in 0.4 Gyr)

APA, Harvard, Vancouver, ISO, and other styles

48

Larqué, Lionel. "Etude des masses d'eau en Atlantique Sud et de la circulation océanique à grande échelle dans le Bassin argentin." Toulouse 3, 1996. http://www.theses.fr/1996TOU30232.

Full text

Abstract:

Nous avons etudie les masses d'eau dans l'atlantique sud et la circulation oceanique dans le bassin argentin. Confirmer les recirculations en surface et au niveau intermediaire ainsi que les transports des courants de bord ouest du bresil et des malouines, conclusions des travaux de maamaatuaiahutapu (1994), constituaient les motivations de cette etude. Nous avons tout d'abord applique la methode semi-quantitative d'analyse multiparametrique developpee par tomczak (1981) aux donnees du programme save (south atlantic ventilation experiment). Cette methode permet de synthetiser les informations fournies par plusieurs traceurs afin de deconvoluer les contributions relatives des masses d'eau en presence dans le bassin argentin: l'eau centrale de l'atlantique sud (sacw ou tw), l'eau subantarctique de surface (sasw), l'eau antarctique intermediaire (aaiw), l'eau profonde nord-atlantique (nadw), l'eau profonde superieure et inferieure du circumpolaire (ucdw et lcdw) et enfin l'eau profonde de la mer de weddell (wsdw). Nous avons, entre autre, montre que l'aaiw ne semblait pas privilegier le parcours le long du bord ouest entre 20 et 40s. Nous avons, dans un second temps, et a des fins quantitative et diagnostic, utilise le modele geostrophique d'inversion non-lineaire de mercier (1986) sur un jeu de donnees historiques. Nous avons affine les connaissances sur la circulation de l'aaiw, la nadw et la wsdw, nous permettant de proposer des schemas de circulation de ces trois masses d'eau sur l'ensemble de l'atlantique sud. La reestimation des courants de bord ouest dans la region du bassin argentin nous a donne les valeurs de 49 sv et 37 sv respectivement pour les courants du bresil et des malouines. Enfin, la recirculation au nord de la region de confluence aux profondeurs intermediaires a ete confirmee, corroborant les conclusions de maamaatuaiahutapu (1994)

APA, Harvard, Vancouver, ISO, and other styles

49

Tran, Viet-Trung. "Sur le passage à l'échelle des systèmes de gestion des grandes masses de données." Phd thesis, École normale supérieure de Cachan - ENS Cachan, 2013. http://tel.archives-ouvertes.fr/tel-00783724.

Full text

Abstract:

La problématique "Big Data" peut être caractérisée par trois "V": * "Big Volume" se rapporte à l'augmentation sans précédent du volume des données. * "Big Velocity" se réfère à la croissance de la vitesse à laquelle ces données sont déplacées entre les systèmes qui les gèrent. * "Big Variety" correspond à la diversification des formats de ces données. Ces caractéristiques imposent des changements fondamentaux dans l'architecture des systèmes de gestion de données. Les systèmes de stockage doivent être adaptés à la croissance des données, et se doivent de passer à l'échelle tout en maintenant un accès à hautes performances. Cette thèse se concentre sur la construction des systèmes de gestion de grandes masses de données passant à l'échelle. Les deux premières contributions ont pour objectif de fournir un support efficace des "Big Volumes" pour les applications data-intensives dans les environnements de calcul à hautes performances (HPC). Nous abordons en particulier les limitations des approches existantes dans leur gestion des opérations d'entrées/sorties (E/S) non-contiguës atomiques à large échelle. Un mécanisme basé sur les versions est alors proposé, et qui peut être utilisé pour l'isolation des E/S non-contiguës sans le fardeau de synchronisations coûteuses. Dans le contexte du traitement parallèle de tableaux multi-dimensionels en HPC, nous présentons Pyramid, un système de stockage large-échelle optimisé pour ce type de données. Pyramid revoit l'organisation physique des données dans les systèmes de stockage distribués en vue d'un passage à l'échelle des performances. Pyramid favorise un partitionnement multi-dimensionel de données correspondant le plus possible aux accès générés par les applications. Il se base également sur une gestion distribuée des métadonnées et un mécanisme de versioning pour la résolution des accès concurrents, ce afin d'éliminer tout besoin de synchronisation. Notre troisième contribution aborde le problème "Big Volume" à l'échelle d'un environnement géographiquement distribué. Nous considérons BlobSeer, un service distribué de gestion de données orienté "versioning", et nous proposons BlobSeer-WAN, une extension de BlobSeer optimisée pour un tel environnement. BlobSeer-WAN prend en compte la hiérarchie de latence et favorise les accès aux méta-données locales. BlobSeer-WAN inclut la réplication asynchrone des méta-données et une résolution des collisions basée sur des "vector-clock". Afin de traîter le caractère "Big Velocity" de la problématique "Big Data", notre dernière contribution consiste en DStore, un système de stockage en mémoire orienté "documents" qui passe à l'échelle verticalement en exploitant les capacités mémoires des machines multi-coeurs. Nous montrons l'efficacité de DStore dans le cadre du traitement de requêtes d'écritures atomiques complexes tout en maintenant un haut débit d'accès en lecture. DStore suit un modèle d'exécution mono-thread qui met à jour les transactions séquentiellement, tout en se basant sur une gestion de la concurrence basée sur le versioning afin de permettre un grand nombre d'accès simultanés en lecture.

APA, Harvard, Vancouver, ISO, and other styles

50

Corte, Vitor Francisco Dalla. "As estratégias e a organização das indústrias de farinha de trigo e de massas alimentícias do Rio Grande do Sul." Universidade Federal de Santa Maria, 2008. http://repositorio.ufsm.br/handle/1/4531.

Full text

Abstract:

The study aims to identify the strategies and the organization of the wheat flour industries and nutritious pastes of Rio Grande do Sul. It is used as theoretical base in the analysis, the production chain, the model structure-conduct-performance (SCP) and Porter s (1980) and Mintzberg s (1988) competitive strategies. In order to accomplish the research the descriptive method was used, with primary (structured questionnaire applied to the companies) and secondary data. The option of restricting the study to Rio Grande do Sul, was due to the fact that the state to be one of the pioneers and now one of the largest producers of wheat flour and nutritious pastes in the country. The results show that the wheat flour industries and of nutritious pastes are located close to one another in the state most them are of medium and small-size companies. It was also observed that both Brazil and Rio Grande do Sul are not self-sufficient in the wheat production thus, making the importation necessary. The main destination to products is the state itself, but the vertical integration in the productive chain is still low. It was also verified that the concentration of the industries falls from 2001 to 2006 and that there are barriers to the important entrance for the incoming in the wheat flour sector, as the minimum scale of production, and the capacity already installed of the companies producing nutritious pastes. Concerning Porter s competitive strategies, the production with lower costs is the most outstanding among the companies producing wheat flour, however, among the nutritious pastes it is the differentiation. Among the Mintzberg s typologies, the quality of the product is considered, by both industries, as being the big competitive differential. The performance of the industries in the analyzed period worsened, because there was profitability decrease and market share loss.
O estudo em questão visa identificar as estratégias e a organização das indústrias de farinha de trigo e de massas alimentícias do Rio Grande do Sul. Utiliza-se como base teórica na análise, a cadeia de produção agroindustrial, o modelo estruturaconduta-desempenho (ECD) e as estratégias competitivas de Porter (1980) e de Mintzberg (1988). Para realização da pesquisa, utilizou-se do método descritivo, com dados primários (questionário estruturado aplicado às empresas) e secundários. A opção de restringir o estudo ao Rio Grande do Sul justifica-se por ser o estado um dos pioneiros e atualmente o terceiro maior produtor de farinha de trigo e um dos maiores produtores de massas alimentícias em âmbito nacional. Os resultados mostram que as indústrias de farinha de trigo e de massas alimentícias localizam-se próximas no estado, e na maioria são de médio e pequeno porte. Além disso, verificou-se que tanto o Brasil como o Rio Grande do Sul não são auto-suficientes na produção de trigo, necessitando de importação. O principal destino dos produtos das indústrias é o próprio Estado, mas a integração vertical na cadeia produtiva ainda é baixa. Constatou-se também que a concentração das indústrias cai de 2002 para 2006 e que existem barreiras à entrada importantes para os ingressantes no setor de farinha de trigo, como a escala mínima de produção, e para os produtores de massas alimentícias, a capacidade já instalada das empresas. Em relação às estratégias competitivas de Porter, a produção com custos mais baixos é a que mais se destaca nas empresas produtoras de farinha de trigo, já nas de massas alimentícias é a diferenciação. Entre as tipologias de Mintzberg, a qualidade do produto é considerada, por ambas as indústrias, como sendo o grande diferencial competitivo. O desempenho das indústrias no período analisado piorou, pois houve queda de lucratividade e perda de participação de mercado.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Graphe massifs'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles