Dissertations / Theses: 'Graph matching'

1

Jin, Wei. "GRAPH PATTERN MATCHING, APPROXIMATE MATCHING AND DYNAMIC GRAPH INDEXING." Case Western Reserve University School of Graduate Studies / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=case1307547974.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Zager, Laura (Laura A. ). "Graph similarity and matching." Thesis, Massachusetts Institute of Technology, 2005. http://hdl.handle.net/1721.1/34119.

Full text

Abstract:

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2005.
Includes bibliographical references (p. 85-88).
Measures of graph similarity have a broad array of applications, including comparing chemical structures, navigating complex networks like the World Wide Web, and more recently, analyzing different kinds of biological data. This thesis surveys several different notions of similarity, then focuses on an interesting class of iterative algorithms that use the structural similarity of local neighborhoods to derive pairwise similarity scores between graph elements. We have developed a new similarity measure that uses a linear update to generate both node and edge similarity scores and has desirable convergence properties. This thesis also explores the application of our similarity measure to graph matching. We attempt to correctly position a subgraph GB within a graph GA using a maximum weight matching algorithm applied to the similarity scores between GA and GB. Significant performance improvements are observed when the topological information provided by the similarity measure is combined with additional information about the attributes of the graph elements and their local neighborhoods. Matching results are presented for subgraph matching within randomly-generated graphs; an appendix briefly discusses matching applications in the yeast interactome, a graph representing protein-protein interactions within yeast.
by Laura Zager.
S.M.

APA, Harvard, Vancouver, ISO, and other styles

3

Zhang, Shijie. "Index-based Graph Querying and Matching in Large Graphs." Cleveland, Ohio : Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1263256028.

Full text

Abstract:

Thesis(Ph.D.)--Case Western Reserve University, 2010
Title from PDF (viewed on 2010-04-12) Department of Electrical Engineering and Computer Science (EECS) Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center

APA, Harvard, Vancouver, ISO, and other styles

4

Solé, Ribalta Albert. "Multiple graph matching and applications." Doctoral thesis, Universitat Rovira i Virgili, 2012. http://hdl.handle.net/10803/86941.

Full text

Abstract:

En aplicaciones de reconocimiento de patrones, los grafos con atributos son en gran medida apropiados. Normalmente, los vértices de los grafos representan partes locales de los objetos i las aristas relaciones entre estas partes locales. No obstante, estas ventajas vienen juntas con un severo inconveniente, la distancia entre dos grafos no puede ser calculada en un tiempo polinómico. Considerando estas características especiales el uso de los prototipos de grafos es necesariamente omnipresente. Las aplicaciones de los prototipos de grafos son extensas, siendo las más habituales clustering, clasificación, reconocimiento de objetos, caracterización de objetos i bases de datos de grafos entre otras. A pesar de la diversidad de aplicaciones de los prototipos de grafos, el objetivo del mismo es equivalente en todas ellas, la representación de un conjunto de grafos. Para construir un prototipo de un grafo todos los elementos del conjunto de enteramiento tienen que ser etiquetados comúnmente. Este etiquetado común consiste en identificar que nodos de que grafos representan el mismo tipo de información en el conjunto de entrenamiento. Una vez este etiquetaje común esta hecho, los atributos locales pueden ser combinados i el prototipo construido. Hasta ahora los algoritmos del estado del arte para calcular este etiquetaje común mancan de efectividad o bases teóricas. En esta tesis, describimos formalmente el problema del etiquetaje global i mostramos una taxonomía de los tipos de algoritmos existentes. Además, proponemos seis nuevos algoritmos para calcular soluciones aproximadas al problema del etiquetaje común. La eficiencia de los algoritmos propuestos es evaluada en diversas bases de datos reales i sintéticas. En la mayoría de experimentos realizados los algoritmos propuestos dan mejores resultados que los existentes en el estado del arte.
In pattern recognition, the use of graphs is, to a great extend, appropriate and advantageous. Usually, vertices of the graph represent local parts of an object while edges represent relations between these local parts. However, its advantages come together with a sever drawback, the distance between two graph cannot be optimally computed in polynomial time. Taking into account this special characteristic the use of graph prototypes becomes ubiquitous. The applicability of graphs prototypes is extensive, being the most common applications clustering, classification, object characterization and graph databases to name some. However, the objective of a graph prototype is equivalent to all applications, the representation of a set of graph. To synthesize a prototype all elements of the set must be mutually labeled. This mutual labeling consists in identifying which nodes of which graphs represent the same information in the training set. Once this mutual labeling is done the set can be characterized and combined to create a graph prototype. We call this initial labeling a common labeling. Up to now, all state of the art algorithms to compute a common labeling lack on either performance or theoretical basis. In this thesis, we formally describe the common labeling problem and we give a clear taxonomy of the types of algorithms. Six new algorithms that rely on different techniques are described to compute a suboptimal solution to the common labeling problem. The performance of the proposed algorithms is evaluated using an artificial and several real datasets. In addition, the algorithms have been evaluated on several real applications. These applications include graph databases and group-wise image registration. In most of the tests and applications evaluated the presented algorithms have showed a great improvement in comparison to state of the art applications.

APA, Harvard, Vancouver, ISO, and other styles

5

Voigt, Konrad. "Structural Graph-based Metamodel Matching." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-81671.

Full text

Abstract:

Data integration has been, and still is, a challenge for applications processing multiple heterogeneous data sources. Across the domains of schemas, ontologies, and metamodels, this imposes the need for mapping specifications, i.e. the task of discovering semantic correspondences between elements. Support for the development of such mappings has been researched, producing matching systems that automatically propose mapping suggestions. However, especially in the context of metamodel matching the result quality of state of the art matching techniques leaves room for improvement. Although the traditional approach of pair-wise element comparison works on smaller data sets, its quadratic complexity leads to poor runtime and memory performance and eventually to the inability to match, when applied on real-world data. The work presented in this thesis seeks to address these shortcomings. Thereby, we take advantage of the graph structure of metamodels. Consequently, we derive a planar graph edit distance as metamodel similarity metric and mining-based matching to make use of redundant information. We also propose a planar graph-based partitioning to cope with large-scale matching. These techniques are then evaluated using real-world mappings from SAP business integration scenarios and the MDA community. The results demonstrate improvement in quality and managed runtime and memory consumption for large-scale metamodel matching.

APA, Harvard, Vancouver, ISO, and other styles

6

Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Lahn, Nathaniel Adam. "A Separator-Based Framework for Graph Matching Problems." Diss., Virginia Tech, 2020. http://hdl.handle.net/10919/98618.

Full text

Abstract:

Given a graph, a matching is a set of vertex-disjoint edges. Graph matchings have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Of particular interest is the problem of finding a maximum cardinality matching of a graph. Also of interest is the weighted variant: the problem of computing a minimum-cost maximum cardinality matching. For an arbitrary graph with m edges and n vertices, there are known, long-standing combinatorial algorithms that compute a maximum cardinality matching in O(m\sqrt{n}) time. For graphs with non-negative integer edge costs at most C, it is known how to compute a minimum-cost maximum cardinality matching in roughly O(m\sqrt{n} log(nC)) time using combinatorial methods. While non-combinatorial methods exist, they are generally impractical and not well understood due to their complexity. As a result, there is great interest in obtaining faster matching algorithms that are purely combinatorial in nature. Improving existing combinatorial algorithms for arbitrary graphs is considered to be a very difficult problem. To make the problem more approachable, it is desirable to make some additional assumptions about the graph. For our work, we make two such assumptions. First, we assume the graph is bipartite. Second, we assume that the graph has a small balanced separator, meaning it is possible to split the graph into two roughly equal-size components by removing a relatively small portion of the graph. Several well-studied classes of graphs have separator-like properties, including planar graphs, minor-free graphs, and geometric graphs. For such graphs, we describe a framework, a general set of techniques for designing efficient algorithms. We demonstrate this framework by applying it to yield polynomial-factor improvements for several open-problems in bipartite matching.
Doctor of Philosophy
Assume we are given a list of objects, and a list of compatible pairs of these objects. A matching consists of a chosen subset of these compatible pairs, where each object participates in at most one chosen pair. For any chosen pair of objects, we say the these two objects are matched. Generally, we seek to maximize the number of compatible matches. A maximum cardinality matching is a matching with the largest possible size. In many cases, there are multiple options for maximizing the number of compatible pairings. While maximizing the size of the matching is often the primary concern, one may also seek to minimize the cost of the matching. This is known as the minimum-cost maximum-cardinality matching problem. These two matching problems have been well studied, since they play a fundamental role in algorithmic theory as well as motivate many practical applications. Our interest is in the design of algorithms for both of these problems that are efficiently scalable, even as the number of objects involved grows very large. To aid in the design of scalable algorithms, we observe that some inputs have good separators, meaning that by removing some subset S of objects, one can divide the remaining objects into two sets V and V', where all pairs of objects between V and V' are incompatible. We design several new algorithms that exploit good separators, and prove that these algorithms scale better than previously existing approaches.

APA, Harvard, Vancouver, ISO, and other styles

8

Ahmed, Algabli Shaima. "Learning the Graph Edit Distance through embedding the graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2020. http://hdl.handle.net/10803/669612.

Full text

Abstract:

Els gràfics són estructures de dades abstractes que s’utilitzen per modelar problemes reals amb dues entitats bàsiques: nodes i vores. Cada node o vèrtex representa un punt d'interès rellevant d'un problema i cada vora representa la relació entre aquests punts. Es poden atribuir nodes i vores per augmentar la precisió del model, cosa que significa que aquests atributs podrien variar des de vectors de característiques fins a etiquetes de descripció. A causa d'aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per ordinador, la biomèdica i l'anàlisi de xarxa, etc., la primera part d'aquesta tesi presenta un mètode general per aprendre automàticament els costos d'edició que comporta l'edició de gràfics. Distància. El mètode es basa en incrustar parells de gràfics i el seu mapeig de node a node de veritat terrestre en un espai euclidià. D’aquesta manera, l’algoritme d’aprenentatge no necessita calcular cap concordança de gràfics tolerant als errors, que és l’inconvenient principal d’altres mètodes a causa de la seva intrínseca complexitat computacional exponencial. No obstant això, el mètode d’aprenentatge té la principal restricció que els costos d’edició han de ser constants. A continuació, posem a prova aquest mètode amb diverses bases de dades gràfiques i també l’aplicem per realitzar el registre d’imatges. A la segona part de la tesi, aquest mètode es particularitza a la verificació d’empremtes dactilars. Les dues diferències principals respecte a l’altre mètode són que només definim els costos d’edició de substitució als nodes. Per tant, suposem que els gràfics no tenen arestes. I també, el mètode d’aprenentatge no es basa en una classificació lineal sinó en una regressió lineal.
Los gráficos son estructuras de datos abstractas que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada borde representa la relación entre estos puntos. Se podrían atribuir nodos y bordes para aumentar la precisión del modelo, lo que significa que estos atributos podrían variar de vectores de características a etiquetas de descripción. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como visión por computadora, biomédicos y análisis de redes, etc. La primera parte de esta tesis presenta un método general para aprender automáticamente los costos de edición involucrados en la Edición de Gráficos Distancia. El método se basa en incrustar pares de gráficos y su mapeo de nodo a nodo de verdad fundamental en un espacio euclidiano. De esta manera, el algoritmo de aprendizaje no necesita calcular ninguna coincidencia de gráfico tolerante a errores, que es el principal inconveniente de otros métodos debido a su complejidad computacional exponencial intrínseca. Sin embargo, el método de aprendizaje tiene la principal restricción de que los costos de edición deben ser constantes. Luego probamos este método con varias bases de datos de gráficos y también lo aplicamos para realizar el registro de imágenes. En la segunda parte de la tesis, este método se especializa en la verificación de huellas digitales. Las dos diferencias principales con respecto al otro método son que solo definimos los costos de edición de sustitución en los nodos. Por lo tanto, suponemos que los gráficos no tienen aristas. Y también, el método de aprendizaje no se basa en una clasificación lineal sino en una regresión lineal.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the model, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, biomedics, and network analysis, and so on .The first part of this thesis presents a general method to automatically learn the edit costs involved in the Graph Edit Distance. The method is based on embedding pairs of graphs and their ground-truth node-tonode mapping into a Euclidean space. In this way, the learning algorithm does not need to compute any Error-Tolerant Graph Matching, which is the main drawback of other methods due to its intrinsic exponential computational complexity. Nevertheless, the learning method has the main restriction that edit costs have to be constant. Then we test this method with several graph databases and also we apply it to perform image registration. In the second part of the thesis, this method is particularized to fingerprint verification. The two main differences with respect to the other method are that we only define the substitution edit costs on the nodes. Thus, we assume graphs do not have edges. And also, the learning method is not based on a linear classification but on a linear regression.

APA, Harvard, Vancouver, ISO, and other styles

9

Wu, Yinghui. "Extending graph homomorphism and simulation for real life graph matching." Thesis, University of Edinburgh, 2011. http://hdl.handle.net/1842/5022.

Full text

Abstract:

Among the vital problems in a variety of emerging applications is the graph matching problem, which is to determine whether two graphs are similar, and if so, find all the valid matches in one graph for the other, based on specified metrics. Traditional graph matching approaches are mostly based on graph homomorphism and isomorphism, falling short of capturing both structural and semantic similarity in real life applications. Moreover, it is preferable while difficult to find all matches with high accuracy over complex graphs. Worse still, the graph structures in real life applications constantly bear modifications. In response to these challenges, this thesis presents a series of approaches for ef?ciently solving graph matching problems, over both static and dynamic real life graphs. Firstly, the thesis extends graph homomorphism and subgraph isomorphism, respectively, by mapping edges from one graph to paths in another, and by measuring the semantic similarity of nodes. The graph similarity is then measured by the metrics based on these extensions. Several optimization problems for graph matching based on the new metrics are studied, with approximation algorithms having provable guarantees on match quality developed. Secondly, although being extended in the above work, graph matching is defined in terms of functions, which cannot capture more meaningful matches and is usually hard to compute. In response to this, the thesis proposes a class of graph patterns, in which an edge denotes the connectivity in a data graph within a predefined number of hops. In addition, the thesis defines graph pattern matching based on a notion of bounded simulation relation, an extension of graph simulation. With this revision, graph pattern matching is in cubic-time by providing such an algorithm, rather than intractable. Thirdly, real life graphs often bear multiple edge types. In response to this, the thesis further extends and generalizes the proposed revisions of graph simulation to a more powerful case: a novel set of reachability queries and graph pattern queries, constrained by a subclass of regular path expressions. Several fundamental problems of the queries are studied: containment, equivalence and minimization. The enriched reachability query does not increase the complexity of the above problems, shown by the corresponding algorithms. Moreover, graph pattern queries can be evaluated in cubic time, where two such algorithms are proposed. Finally, real life graphs are frequently updated with small changes. The thesis investigates incremental algorithms for graph pattern matching defined in terms of graph simulation, bounded simulation and subgraph isomorphism. Besides studying the results on the complexity bounds, the thesis provides the experimental study verifying that these incremental algorithms significantly outperform their batch counterparts in response to small changes, using real-life data and synthetic data.

APA, Harvard, Vancouver, ISO, and other styles

10

Wilson, Richard Charles. "Inexact graph matching using symbolic constraints." Thesis, University of York, 1996. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.297165.

Full text

APA, Harvard, Vancouver, ISO, and other styles

11

Nikjoo, Soukhtabandani Ali. "Partial shape matching using CCP map and weighted graph transformation matching." Thesis, Université Laval, 2014. http://www.theses.ulaval.ca/2014/30611/30611.pdf.

Full text

Abstract:

La détection de la similarité ou de la différence entre les images et leur mise en correspondance sont des problèmes fondamentaux dans le traitement de l'image. Pour résoudre ces problèmes, on utilise, dans la littérature, différents algorithmes d'appariement. Malgré leur nouveauté, ces algorithmes sont pour la plupart inefficaces et ne peuvent pas fonctionner correctement dans les situations d’images bruitées. Dans ce mémoire, nous résolvons la plupart des problèmes de ces méthodes en utilisant un algorithme fiable pour segmenter la carte des contours image, appelée carte des CCPs, et une nouvelle méthode d'appariement. Dans notre algorithme, nous utilisons un descripteur local qui est rapide à calculer, est invariant aux transformations affines et est fiable pour des objets non rigides et des situations d’occultation. Après avoir trouvé le meilleur appariement pour chaque contour, nous devons vérifier si ces derniers sont correctement appariés. Pour ce faire, nous utilisons l'approche « Weighted Graph Transformation Matching » (WGTM), qui est capable d'éliminer les appariements aberrants en fonction de leur proximité et de leurs relations géométriques. WGTM fonctionne correctement pour les objets à la fois rigides et non rigides et est robuste aux distorsions importantes. Pour évaluer notre méthode, le jeu de données ETHZ comportant cinq classes différentes d'objets (bouteilles, cygnes, tasses, girafes, logos Apple) est utilisé. Enfin, notre méthode est comparée à plusieurs méthodes célèbres proposées par d'autres chercheurs dans la littérature. Bien que notre méthode donne un résultat comparable à celui des méthodes de référence en termes du rappel et de la précision de localisation des frontières, elle améliore significativement la précision moyenne pour toutes les catégories du jeu de données ETHZ.
Matching and detecting similarity or dissimilarity between images is a fundamental problem in image processing. Different matching algorithms are used in literature to solve this fundamental problem. Despite their novelty, these algorithms are mostly inefficient and cannot perform properly in noisy situations. In this thesis, we solve most of the problems of previous methods by using a reliable algorithm for segmenting image contour map, called CCP Map, and a new matching method. In our algorithm, we use a local shape descriptor that is very fast, invariant to affine transform, and robust for dealing with non-rigid objects and occlusion. After finding the best match for the contours, we need to verify if they are correctly matched. For this matter, we use the Weighted Graph Transformation Matching (WGTM) approach, which is capable of removing outliers based on their adjacency and geometrical relationships. WGTM works properly for both rigid and non-rigid objects and is robust to high order distortions. For evaluating our method, the ETHZ dataset including five diverse classes of objects (bottles, swans, mugs, giraffes, apple-logos) is used. Finally, our method is compared to several famous methods proposed by other researchers in the literature. While our method shows a comparable result to other benchmarks in terms of recall and the precision of boundary localization, it significantly improves the average precision for all of the categories in the ETHZ dataset.

APA, Harvard, Vancouver, ISO, and other styles

12

Wang, Xin. "Graph pattern matching on social network analysis." Thesis, University of Edinburgh, 2013. http://hdl.handle.net/1842/8277.

Full text

Abstract:

Graph pattern matching is fundamental to social network analysis. Its effectiveness for identifying social communities and social positions, making recommendations and so on has been repeatedly demonstrated. However, the social network analysis raises new challenges to graph pattern matching. As real-life social graphs are typically large, it is often prohibitively expensive to conduct graph pattern matching over such large graphs, e.g., NP-complete for subgraph isomorphism, cubic time for bounded simulation, and quadratic time for simulation. These hinder the applicability of graph pattern matching on social network analysis. In response to these challenges, the thesis presents a series of effective techniques for querying large, dynamic, and distributively stored social networks. First of all, we propose a notion of query preserving graph compression, to compress large social graphs relative to a class Q of queries. We then develop both batch and incremental compression strategies for two commonly used pattern queries. Via both theoretical analysis and experimental studies, we show that (1) using compressed graphs Gr benefits graph pattern matching dramatically; and (2) the computation of Gr as well as its maintenance can be processed efficiently. Secondly, we investigate the distributed graph pattern matching problem, and explore parallel computation for graph pattern matching. We show that our techniques possess following performance guarantees: (1) each site is visited only once; (2) the total network traffic is independent of the size of G; and (3) the response time is decided by the size of largest fragment of G rather than the size of entire G. Furthermore, we show how these distributed algorithms can be implemented in the MapReduce framework. Thirdly, we study the problem of answering graph pattern matching using views since view based techniques have proven an effective technique for speeding up query evaluation. We propose a notion of pattern containment to characterise graph pattern matching using views, and introduce efficient algorithms to answer graph pattern matching using views. Moreover, we identify three problems related to graph pattern containment, and provide efficient algorithms for containment checking (approximation when the problem is intractable). Fourthly, we revise graph pattern matching by supporting a designated output node, which we treat as “query focus”. We then introduce algorithms for computing the top-k relevant matches w.r.t. the output node for both acyclic and cyclic pattern graphs, respectively, with early termination property. Furthermore, we investigate the diversified top-k matching problem, and develop an approximation algorithm with performance guarantee and a heuristic algorithm with early termination property. Finally, we introduce an expert search system, called ExpFinder, for large and dynamic social networks. ExpFinder identifies top-k experts in social networks by graph pattern matching, and copes with the sheer size of real-life social networks by integrating incremental graph pattern matching, query preserving compression and top-k matching computation. In particular, we also introduce bounded (resp. unbounded) incremental algorithms to maintain the weighted landmark vectors which are used for incremental maintenance for cached results.

APA, Harvard, Vancouver, ISO, and other styles

13

Dahm, Nicholas. "Advances in Graph Matching for Image Interpretation." Thesis, Griffith University, 2015. http://hdl.handle.net/10072/365647.

Full text

Abstract:

In structural pattern recognition, graphs are a powerful and flexible data structure, allowing for the description of complex relationships between data elements. This flexibility comes at a cost, as the unconstrained nature of graphs results in a high computational complexity for graph matching algorithms. Various algorithms have been proposed to mitigate this complexity and make graph matching tractable. Additionally, in domains where the number of graph nodes is low, or where the data provides additional constraints, such as node and edge labels, graph matching has been effectively applied. Such applications include chemical structure matching, protein-protein interaction networks, and network analysis. In the domain of computer vision, graphs have been successfully applied to a number a problems including image segmentation, partitioning, and matching. However, for practical reasons, many of the image matching techniques that utilise graphs do not match graph topology directly. Instead, image graphs are used only to constrain feature locations, or spectral embedding is used to transform image graphs into vectors, which are then matched.
Thesis (PhD Doctorate)
Doctor of Philosophy (PhD)
Griffith School of Engineering
Science, Environment, Engineering and Technology
Full Text

APA, Harvard, Vancouver, ISO, and other styles

14

Yang, Cheng. "Graph by Example: an Exploratory Graph Query Interface for RDF Databases." Case Western Reserve University School of Graduate Studies / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1445863762.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Ngo, Duy Hoa. "Enhancing Ontology Matching by Using Machine Learning, Graph Matching and Information Retrieval Techniques." Thesis, Montpellier 2, 2012. http://www.theses.fr/2012MON20096/document.

Full text

Abstract:

Ces dernières années, les ontologies ont suscité de nombreux travaux dans le domaine du web sémantique. Elles sont utilisées pour fournir le vocabulaire sémantique permettant de rendre la connaissance du domaine disponible pour l'échange et l'interprétation au travers des systèmes d'information. Toutefois, en raison de la nature décentralisée du web sémantique, les ontologies sont très hétérogènes. Cette hétérogénéité provoque le problème de la variation de sens ou ambiguïté dans l'interprétation des entités et, par conséquent, elle empêche le partage des connaissances du domaine. L'alignement d'ontologies, qui a pour but la découverte des correspondances sémantiques entre des ontologies, devient une tâche cruciale pour résoudre ce problème d'hétérogénéité dans les applications du web sémantique. Les principaux défis dans le domaine de l'alignement d'ontologies ont été décrits dans des études récentes. Parmi eux, la sélection de mesures de similarité appropriées ainsi que le réglage de la configuration de leur combinaison sont connus pour être des problèmes fondamentaux que la communauté doit traiter. En outre, la vérification de la cohérence sémantique des correspondances est connue pour être une tâche importante. Par ailleurs, la difficulté du problème augmente avec la taille des ontologies. Pour faire face à ces défis, nous proposons dans cette thèse une nouvelle approche, qui combine différentes techniques issues des domaines de l'apprentissage automatique, d'appariement de graphes et de recherche d'information en vue d'améliorer la qualité de l'alignement d'ontologies. En effet, nous utilisons des techniques de recherche d'information pour concevoir de nouvelles mesures de similarité efficaces afin de comparer les étiquettes et les profils d'entités de contexte au niveau des entités. Nous appliquons également une méthode d'appariement de graphes appelée propagation de similarité au niveau de la structure qui découvre effectivement des correspondances en exploitant des informations structurelles des entités. Pour combiner les mesures de similarité au niveau des entités, nous transformons la tâche de l'alignement d'ontologie en une tâche de classification de l'apprentissage automatique. Par ailleurs, nous proposons une méthode dynamique de la somme pondérée pour combiner automatiquement les correspondances obtenues au niveau des entités et celles obtenues au niveau de la structure. Afin d'écarter les correspondances incohérentes, nous avons conçu une nouvelle méthode de filtrage sémantique. Enfin, pour traiter le problème de l'alignement d'ontologies à large échelle, nous proposons deux méthodes de sélection des candidats pour réduire l'espace de calcul.Toutes ces contributions ont été mises en œuvre dans un prototype nommé YAM++. Pour évaluer notre approche, nous avons utilisé des données du banc d'essai de la compétition OAEI : Benchmark, Conference, Multifarm, Anatomy, Library and Large Biomedical Ontologies. Les résultats expérimentaux montrent que les méthodes proposées sont très efficaces. De plus, en comparaison avec les autres participants à la compétition OAEI, YAM++ a montré sa compétitivité et a acquis une position de haut rang
In recent years, ontologies have attracted a lot of attention in the Computer Science community, especially in the Semantic Web field. They serve as explicit conceptual knowledge models and provide the semantic vocabularies that make domain knowledge available for exchange and interpretation among information systems. However, due to the decentralized nature of the semantic web, ontologies are highlyheterogeneous. This heterogeneity mainly causes the problem of variation in meaning or ambiguity in entity interpretation and, consequently, it prevents domain knowledge sharing. Therefore, ontology matching, which discovers correspondences between semantically related entities of ontologies, becomes a crucial task in semantic web applications.Several challenges to the field of ontology matching have been outlined in recent research. Among them, selection of the appropriate similarity measures as well as configuration tuning of their combination are known as fundamental issues that the community should deal with. In addition, verifying the semantic coherent of the discovered alignment is also known as a crucial task. Furthermore, the difficulty of the problem grows with the size of the ontologies. To deal with these challenges, in this thesis, we propose a novel matching approach, which combines different techniques coming from the fields of machine learning, graph matching and information retrieval in order to enhance the ontology matching quality. Indeed, we make use of information retrieval techniques to design new effective similarity measures for comparing labels and context profiles of entities at element level. We also apply a graph matching method named similarity propagation at structure level that effectively discovers mappings by exploring structural information of entities in the input ontologies. In terms of combination similarity measures at element level, we transform the ontology matching task into a classification task in machine learning. Besides, we propose a dynamic weighted sum method to automatically combine the matching results obtained from the element and structure level matchers. In order to remove inconsistent mappings, we design a new fast semantic filtering method. Finally, to deal with large scale ontology matching task, we propose two candidate selection methods to reduce computational space.All these contributions have been implemented in a prototype named YAM++. To evaluate our approach, we adopt various tracks namely Benchmark, Conference, Multifarm, Anatomy, Library and Large BiomedicalOntologies from the OAEI campaign. The experimental results show that the proposed matching methods work effectively. Moreover, in comparison to other participants in OAEI campaigns, YAM++ showed to be highly competitive and gained a high ranking position

APA, Harvard, Vancouver, ISO, and other styles

16

Cherchago, Alexey. "Service specification and matching based on graph transformation." [S.l.] : [s.n.], 2006. http://deposit.ddb.de/cgi-bin/dokserv?idn=980143039.

Full text

APA, Harvard, Vancouver, ISO, and other styles

17

Klinger, Stefan. "Chemical similarity searching with neural graph matching methods." Thesis, University of York, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.425461.

Full text

APA, Harvard, Vancouver, ISO, and other styles

18

Fang, Yan. "Data clustering and graph-based image matching methods." Thesis, University of York, 2012. http://etheses.whiterose.ac.uk/4778/.

Full text

Abstract:

This thesis describes our novel methods for data clustering, graph characterizing and image matching. In Chapter 3, our main contribution is the M1NN agglomerative clustering method with a new parallel merging algorithm. A cluster characterizing quantity is derived from the path-based dissimilarity measure. In Chapter 4, our main contribution is the modified log likelihood model for quantitative clustering analysis. The energy of a graph is adopted to define the description length to measure the complexity of a clustering. In Chapter 5, our main contribution is an image matching method based on Delaunay graph characterization and node selection. A normalized Euclidean distance on Delaunay graphs is found useful to estimate pairwise distances.

APA, Harvard, Vancouver, ISO, and other styles

19

Santacruz, Muñoz José Luis. "Error-tolerant Graph Matching on Huge Graphs and Learning Strategies on the Edit Costs." Doctoral thesis, Universitat Rovira i Virgili, 2019. http://hdl.handle.net/10803/668356.

Full text

Abstract:

Els grafs són estructures de dades abstractes que s'utilitzen per a modelar problemes reals amb dues entitats bàsiques: nodes i arestes. Cada node o vèrtex representa un punt d'interès rellevant d'un problema, i cada aresta representa la relació entre aquests vèrtexs. Els nodes i les arestes podrien incorporar atributs per augmentar la precisió del problema modelat. Degut a aquesta versatilitat, s'han trobat moltes aplicacions en camps com la visió per computador, biomèdics, anàlisi de xarxes, etc. La Distància d'edició de grafs (GED) s'ha convertit en una eina important en el reconeixement de patrons estructurals, ja que permet mesurar la dissimilitud dels grafs. A la primera part d'aquesta tesi es presenta un mètode per generar una parella grafs juntament amb la seva correspondència en un cost computacional lineal. A continuació, se centra en com mesurar la dissimilitud entre dos grafs enormes (més de 10.000 nodes), utilitzant un nou algoritme de aparellament de grafs anomenat Belief Propagation. Té un cost computacional O(d^3.5N). Aquesta tesi també presenta un marc general per aprendre els costos d'edició implicats en els càlculs de la GED automàticament. Després, concretem aquest marc en dos models diferents basats en xarxes neuronals i funcions de densitat de probabilitat. S'ha realitzat una validació pràctica exhaustiva en 14 bases de dades públiques. Aquesta validació mostra que la precisió és major amb els costos d'edició apresos, que amb alguns costos impostos manualment o altres costos apresos automàticament per mètodes anteriors. Finalment proposem una aplicació de l'algoritme Belief propagation utilitzat en la simulació de la mecànica muscular.
Los grafos son estructuras de datos abstractos que se utilizan para modelar problemas reales con dos entidades básicas: nodos y aristas. Cada nodo o vértice representa un punto de interés relevante de un problema, y cada arista representa la relación entre estos vértices. Los nodos y las aristas podrían incorporar atributos para aumentar la precisión del problema modelado. Debido a esta versatilidad, se han encontrado muchas aplicaciones en campos como la visión por computador, biomédicos, análisis de redes, etc. La Distancia de edición de grafos (GED) se ha convertido en una herramienta importante en el reconocimiento de patrones estructurales, ya que permite medir la disimilitud de los grafos. En la primera parte de esta tesis se presenta un método para generar una pareja grafos junto con su correspondencia en un coste computacional lineal. A continuación, se centra en cómo medir la disimilitud entre dos grafos enormes (más de 10.000 nodos), utilizando un nuevo algoritmo de emparejamiento de grafos llamado Belief Propagation. Tiene un coste computacional O(d^3.5n). Esta tesis también presenta un marco general para aprender los costos de edición implicados en los cálculos de GED automáticamente. Luego, concretamos este marco en dos modelos diferentes basados en redes neuronales y funciones de densidad de probabilidad. Se ha realizado una validación práctica exhaustiva en 14 bases de datos públicas. Esta validación muestra que la precisión es mayor con los costos de edición aprendidos, que con algunos costos impuestos manualmente u otros costos aprendidos automáticamente por métodos anteriores. Finalmente proponemos una aplicación del algoritmo Belief propagation utilizado en la simulación de la mecánica muscular.
Graphs are abstract data structures used to model real problems with two basic entities: nodes and edges. Each node or vertex represents a relevant point of interest of a problem, and each edge represents the relationship between these points. Nodes and edges could be attributed to increase the accuracy of the modeled problem, which means that these attributes could vary from feature vectors to description labels. Due to this versatility, many applications have been found in fields such as computer vision, bio-medics, network analysis, etc. Graph Edit Distance (GED) has become an important tool in structural pattern recognition since it allows to measure the dissimilarity of attributed graphs. The first part presents a method is presented to generate graphs together with an upper and lower bound distance and a correspondence in a linear computational cost. Through this method, the behaviour of the known -or the new- sub-optimal Error-Tolerant graph matching algorithm can be tested against a lower and an upper bound GED on large graphs, even though we do not have the true distance. Next, the present is focused on how to measure the dissimilarity between two huge graphs (more than 10.000 nodes), using a new Error-Tolerant graph matching algorithm called Belief Propagation algorithm. It has a O(d^3.5n) computational cost.This thesis also presents a general framework to learn the edit costs involved in the GED calculations automatically. Then, we concretise this framework in two different models based on neural networks and probability density functions. An exhaustive practical validation on 14 public databases has been performed. This validation shows that the accuracy is higher with the learned edit costs, than with some manually imposed costs or other costs automatically learned by previous methods. Finally we propose an application of the Belief propagation algorithm applied to muscle mechanics.

APA, Harvard, Vancouver, ISO, and other styles

20

Li, Jie. "Data integration for biological network databases MetNetDB labeled graph model and graph matching algorithm /." [Ames, Iowa : Iowa State University], 2008.

Find full text

APA, Harvard, Vancouver, ISO, and other styles

21

Sartipi, Kamran. "Software Architecture Recovery based on Pattern Matching." Thesis, University of Waterloo, 2003. http://hdl.handle.net/10012/1122.

Full text

Abstract:

Pattern matching approaches in reverse engineering aim to incorporate domain knowledge and system documentation in the software architecture extraction process, hence provide a user/tool collaborative environment for architectural design recovery. This thesis presents a model and an environment for recovering the high level design of legacy software systems based on user defined architectural patterns and graph matching techniques. In the proposed model, a high-level view of a software system in terms of the system components and their interactions is represented as a query, using a description language. A query is mapped onto a pattern-graph, where a module and its interactions with other modules are represented as a group of graph-nodes and a group of graph-edges, respectively. Interaction constraints can be modeled by the description language as a part of the query. Such a pattern-graph is applied against an entity-relation graph that represents the information extracted from the source code of the software system. An approximate graph matching process performs a series of graph edit operations (i. e. , node/edge insertion/deletion) on the pattern-graph and uses a ranking mechanism based on data mining association to obtain a sub-optimal solution. The obtained solution corresponds to an extracted architecture that complies with the given query. An interactive prototype toolkit implemented as part of this thesis provides an environment for architecture recovery in two levels. First the system is decomposed into a number of subsystems of files. Second each subsystem can be decomposed into a number of modules of functions, datatypes, and variables.

APA, Harvard, Vancouver, ISO, and other styles

22

Lee, Victor Eugene. "RoleSim and RoleMatch: Role-Based Similarity and Graph Matching." Kent State University / OhioLINK, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=kent1345064156.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Kolli, Lakshmi Priya. "Mining for Frequent Community Structures using Approximate Graph Matching." University of Cincinnati / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1623166375110273.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Bodas, Shalmali Vidyadhar. "Improved association graph matching of intra-patient airway trees." Thesis, University of Iowa, 2008. https://ir.uiowa.edu/etd/197.

Full text

Abstract:

Pulmonary diseases are frequently associated with changes in lung anatomy. These diseases may change the airway, vessel and lung tissue properties. In order to evaluate the lung in a longitudinal study, a stable reference system is required to identify corresponding parts of the lung. The structure of the airway tree can be used to repeatedly identify the regions of interest. In this study, an improved method for matching of intra-patient airway trees was proposed and evaluated. The association graph method proposed by Pelillo et al. matches free and rooted trees by detecting the maximal sub-tree isomorphism. Tschirren et al. implemented this approach for labeling and matching of human airway trees and reported 92.9% matching accuracy which is the highest among existing methods. However we recognized a few shortcomings of this method. When we tested it on seven normal human cases, we observed that successful matching relies heavily on the accurate labeling of main branchpoints in the trees. Incorrect labeling of main branch points or failure in labeling results in failure to match that branch point. Such matching errors may eventually propagate to sub-trees. On our seven data samples, matching accuracy was found to be as low as 65%. To improve the matching performance, we propose to make matching independent of labeling as well as improve association graph by adding constraint of path-length along with the existing constraints. Furthermore, we would like to redefine the incorrect matches as those matches which are mismatched as well as those that are missed by the matching algorithm. Our results for a total of 27 cases show a significant improvement in accuracy. The accuracy calculated as per the convention without accounting for the branchpoint pairs missed by the algorithm is 92.19% whereas the accuracy calculated as per our definition is 73.98%, with runtime in the range of 0.01-262.81 sec (average runtime is 25.14 sec). We thus propose an improved association graph method which is efficient in matching intra-patient airway trees with good accuracy and within a reasonable time.

APA, Harvard, Vancouver, ISO, and other styles

25

Guevara, Jaime Garcia. "Biomechanical graph matching for hepatic intra-operative image registration." Electronic Thesis or Diss., Université de Lorraine, 2019. http://www.theses.fr/2019LORR0238.

Full text

Abstract:

La première contribution proposée est d’abord de remplacer l’estimation de la transformation faite par GPR par un modèle biomécanique de l’organe, avec l’idée qu’une estimation plus proche de la physique permet de mieux éliminer les hypothèses erronées (Garcia Guevara et al., 2018). Cette méthode appelée BGM permet de réduire l’erreur de recalage mais elle reste peu robuste au bruit et a encore un coût de calcul trop élevé. L’utilisation d’une mise en correspondance basée sur la compliance est la seconde contribution de ce chapitre. Deux algorithmes ont ainsi été développés. VCGM est basé sur le modèle vascularisé du foie pour le calcul de la transformation et le calcul de la compliance. L’introduction de la mise en correspondance basée sur la compliance s’est révélé beaucoup plus efficace que l’usage de la covariance. La méthode développée ensuite, appelée ACGM, vise à réduire encore le temps de calcul grâce à une stratégie adaptative consistant à développer en premier lieu les hypothèses de mise en correspondances les plus plausibles. Cette stratégie réduit par ailleurs la sensibilité de l’algorithme au choix des paramètres de la méthode et améliore la qualité du recalage. Les méthodes utilisées ont été testées avec des jeux de données synthétiques ainsi que sur des données réelles avec comme données préopératoires des scanners et pour données per-opératoires des images CBCT et ultrasons 3D
This thesis presents the development of an automatic elastic registration method based on matching of vascular graphs extracted from both pre-operative and intra-operative images. The method can fuse accurate pre-operative information onto an organ undergoing small to large deformations during surgery, to compensate for the limited details provided by intra-operative imaging modalities and improve the visualization of tumor(s), vasculature and other important internal structures. Although methods dedicated to non-rigid graph matching exist, they are not efficient when noise, topology changes, and large intra-operative deformations are present. The first contribution presented is a biomechanical graph matching method (BGM) that builds on the work of Serradell et al. (2015). BGM combines the Gaussian Process Regression (GPR) matching with a biomechanical model of the organ, as a mean to discard matching hypotheses which would lead to non-plausible deformations (Garcia Guevara et al., 2018). However, BGM is not robust to noise, only matches limited size graphs and has a high computation time. The second contribution is the Adaptive Compliance Graph Matching (ACGM) method (Garcia Guevara et al., 2019), which allows to efficiently find the best graph matches with a novel compliance-based search and an adaptive rigid to soft approach. This reduces the computation time by predicting first the most plausible matching hypotheses. It also reduces the sensitivity on the search space parameters and improves the registration quality. The proposed registration methods are evaluated with realistic synthetic and real porcine datasets, showing that ACGM is compatible with intra-operative constraints

APA, Harvard, Vancouver, ISO, and other styles

26

Jupin, Joseph. "Temporal Graph Record Linkage and k-Safe Approximate Match." Diss., Temple University Libraries, 2016. http://cdm16002.contentdm.oclc.org/cdm/ref/collection/p245801coll10/id/412419.

Full text

Abstract:

Computer and Information Science
Ph.D.
Since the advent of electronic data processing, organizations have accrued vast amounts of data contained in multiple databases with no reliable global unique identifier. These databases were developed by different departments for different purposes at different times. Organizing and analyzing these data for human services requires linking records from all sources. RL (Record Linkage) is a process that connects records that are related to the identical or a sufficiently similar entity from multiple heterogeneous databases. RL is a data and compute intensive, mission critical process. The process must be efficient enough to process big data and effective enough to provide accurate matches. We have evaluated an RL system that is currently in use by a local health and human services department. We found that they were using the typical approach that was offered by Fellegi and Sunter with tuple-by-tuple processing, using the Soundex as the primary approximate string matching method. The Soundex has been found to be unreliable both as a phonetic and as an approximate string matching method. We found that their data, in many cases, has more than one value per field, suggesting that the data were queried from a 5NF data base. Consider that if a woman has been married 3 times, she may have up to 4 last names on record. This query process produced more than one tuple per database/entity apparently generating a Cartesian product of this data. In many cases, more than a dozen tuples were observed for a single database/entity. This approach is both ineffective and inefficient. An effective RL method should handle this multi-data without redundancy and use edit-distance for approximate string matching. However, due to high computational complexity, edit-distance will not scale well with big data problems. We developed two methodologies for resolving the aforementioned issues: PSH and ALIM. PSH – The Probabilistic Signature Hash is a composite method that increases the speed of Damerau-Levenshtein edit-distance. It combines signature filtering, probabilistic hashing, length filtering and prefix pruning to increase the speed of edit-distance. It is also lossless because it does not lose any true positive matches. ALIM – Aggregate Link and Iterative Match is a graph-based record linkage methodology that uses a multi-graph to store demographic data about people. ALIM performs string matching as records are inserted into the graph. ALIM eliminates data redundancy and stores the relationships between data. We tested PSH for string comparison and found it to be approximately 6,000 times faster than DL. We tested it against the trie-join methods and found that they are up to 6.26 times faster but lose between 10 and 20 percent of true positives. We tested ALIM against a method currently in use by a local health and human services department and found ALIM to produce significantly more matches (even with more restrictive match criteria) and that ALIM ran more than twice as fast. ALIM handles the multi-data problem and PSH allows the use of edit-distance comparison in this RL model. ALIM is more efficient and effective than a currently implemented RL system. This model can also be expanded to perform social network analysis and temporal data modeling. For human services, temporal modeling can reveal how policy changes and treatments affect clients over time and social network analysis can determine the effects of these on whole families by facilitating family linkage.
Temple University--Theses

APA, Harvard, Vancouver, ISO, and other styles

27

Norine, Serguei. "Matching structure and Pfaffian orientations of graphs." Diss., Georgia Institute of Technology, 2005. http://hdl.handle.net/1853/7232.

Full text

Abstract:

The first result of this thesis is a generation theorem for bricks. A brick is a 3-connected graph such that the graph obtained from it by deleting any two distinct vertices has a perfect matching. The importance of bricks stems from the fact that they are building blocks of a decomposition procedure of Kotzig, and Lovasz and Plummer. We prove that every brick except for the Petersen graph can be generated from K_4 or the prism by repeatedly applying certain operations in such a way that all the intermediate graphs are bricks. We use this theorem to prove an exact upper bound on the number of edges in a minimal brick with given number of vertices and to prove that every minimal brick has at least three vertices of degree three. The second half of the thesis is devoted to an investigation of graphs that admit Pfaffian orientations. We prove that a graph admits a Pfaffian orientation if and only if it can be drawn in the plane in such a way that every perfect matching crosses itself even number of times. Using similar techniques, we give a new proof of a theorem of Kleitman on the parity of crossings and develop a new approach to Turan's problem of estimating crossing number of complete bipartite graphs. We further extend our methods to study k-Pfaffian graphs and generalize a theorem by Gallucio, Loebl and Tessler. Finally, we relate Pfaffian orientations and signs of edge-colorings and prove a conjecture of Goddyn that every k-edge-colorable k-regular Pfaffian graph is k-list-edge-colorable. This generalizes a theorem of Ellingham and Goddyn for planar graphs.

APA, Harvard, Vancouver, ISO, and other styles

28

Qiao, Shi. "QUERYING GRAPH STRUCTURED RDF DATA." Case Western Reserve University School of Graduate Studies / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=case1447198654.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Ferrer, Sumsi Miquel. "Theory and Algorithms on the Median Graph. Application to Graph-based Classification and Clustering." Doctoral thesis, Universitat Autònoma de Barcelona, 2008. http://hdl.handle.net/10803/5788.

Full text

Abstract:

Donat un conjunt d'objectes, el concepte genèric de mediana està deﬁnit com l'objecte amb la suma de distàncies a tot el conjunt, més petita. Sovint, aquest concepte és usat per a obtenir el representant del conjunt.
En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana és conegut com median graph. Potencialment, té les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs.
Tot i la seva simple deﬁnició i les potencials aplicacions, s'ha demostrat que el seu càlcul és una tasca extremadament complexa. Tots els algorismes existents només han estat capaços de treballar amb conjunts petits de grafs, i per tant, la seva aplicació ha estat limitada en molts casos a usar dades sintètiques sense signiﬁcat real. Així, tot i el seu potencial, ha restat com un concepte eminentment teòric.
L'objectiu principal d'aquesta tesi doctoral és el d'investigar a fons la teoria i l'algorísmica relacionada amb el concepte de medinan graph, amb l'objectiu ﬁnal d'extendre la seva aplicabilitat i lliurar tot el seu potencial al món de les aplicacions reals. Per això, presentem nous resultats teòrics i també nous algorismes per al seu càlcul. Des d'un punt de vista teòric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teòriques del median graph poden ser millorades sota determinades condicions. Més enllà de les aportacioncs teòriques, proposem cinc noves alternatives per al seu càlcul. La primera d'elles és una conseqüència directa del concepte d'spectral median graph. Després, basats en les millores de les propietats teòriques, presentem dues alternatives més per a la seva obtenció. Finalment, s'introdueix una nova tècnica per al càlcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes més.
L'avaluació experimental dels mètodes proposats utilitzant una base de dades semi-artiﬁcial (símbols gràﬁcs) i dues amb dades reals (mollècules i pàgines web), mostra que aquests mètodes són molt més eﬁcients que els existents. A més, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classiﬁcació i clustering que validen aquesta hipòtesi i permeten preveure una pròspera aplicació del median graph a un bon nombre d'algorismes d'aprenentatge.
Given a set of objects, the generic concept of median is deﬁned as the object with the smallest sum of distances to all the objects in the set. It has been often used as a good alternative to obtain a representative of the set.
In structural pattern recognition, graphs are normally used to represent structured objects. In the graph domain, the concept analogous to the median is known as the median graph. By extension, it has the same potential applications as the generic median in order to be used as the representative of a set of graphs.
Despite its simple deﬁnition and potential applications, its computation has been shown as an extremely complex task. All the existing algorithms can only deal with small sets of graphs, and its application has been constrained in most cases to the use of synthetic data with no real meaning. Thus, it has mainly remained in the box of the theoretical concepts.
The main objective of this work is to further investigate both the theory and the algorithmic underlying the concept of the median graph with the ﬁnal objective to extend its applicability and bring all its potential to the world of real applications. To this end, new theory and new algorithms for its computation are reported. From a theoretical point of view, this thesis makes two main contributions. On one hand, the new concept of spectral median graph. On the other hand, we show that some of the existing theoretical properties of the median graph can be improved under some speciﬁc conditions. In addition to these theoretical contributions, we propose ﬁve new ways to compute the median graph. One of them is a direct consequence of the spectral median graph concept. In addition, we provide two new algorithms based on the new theoretical properties. Finally, we present a novel technique for the median graph computation based on graph embedding into vector spaces. With this technique two more new algorithms are presented.
The experimental evaluation of the proposed methods on one semi-artiﬁcial and two real-world datasets, representing graphical symbols, molecules and webpages, shows that these methods are much more ecient than the existing ones. In addition, we have been able to proof for the ﬁrst time that the median graph can be a good representative of a class in large datasets. We have performed some classiﬁcation and clustering experiments that validate this hypothesis and permit to foresee a successful application of the median graph to a variety of machine learning algorithms.

APA, Harvard, Vancouver, ISO, and other styles

30

Cortés, Llosa Xavier. "Active and interactive learning strategies for error-tolerant graph matching." Doctoral thesis, Universitat Rovira i Virgili, 2016. http://hdl.handle.net/10803/396314.

Full text

Abstract:

Els grafs, són un tipus de dades que ens permet emmagatzemar la informació estructural d’un objecte conferint-nos la possibilitat de representar patrons que degut a la seva pròpia naturalesa requereixen d’aquesta particularitat, ja siguin imatges, estructures químiques o biològiques, xarxes, patrons biomètrics... Des de fa més de 30 anys, la recerca enfocada a com representar objectes mitjançant grafs i el posterior còmput de la distància entre aquestes representacions ha ocupat el treball de molts investigadors. La definició d’un model adequat per mesurar la dissimilitud entre dues d’aquestes representacions, és una qüestió clau en el camp del reconeixement de patrons. A aquest problema se l’ha anomenat “Error-Tolerant Graph Matching”. La “Graph Edit Distance” és una aproximació particular al problema de “l’Error-Tolerant Graph Matching” a partir del còmput de la mínima distorsió necessària per transformar un graf en un altre. El principal objectiu d’aquesta tesi, és el de proposar un nou model per aprendre automàticament els paràmetres de la “Graph Edit Distance” i definir diferents estratègies actives d’aprenentatge per afegir interactivitat al problema. Aquesta tesi, també explora la definició de diferents mètriques per calcular la dissimilitud entre sub-estructures locals corresponents a dos nodes i presenta un nou model basat en “metric-trees” de “Graph Class Prototypes” per guardar col•leccions de grafs. Finalment, es proposa portar el concepte d’interactivitat a un altre domini, el problema de relacionar els punts entre dues imatges per tal de millorar la precisió en el càlcul de la posició correlativa entre robots pertanyents a una mateixa flota que treballa de forma cooperativa.
Los grafos, son un tipo de datos que nos permite almacenar la información estructural de un objeto confiriéndole la posibilidad de representar patrones que debido a su propia naturaleza requieren de esta particularidad, ya sean imágenes, estructuras químicas o biológicas, redes , patrones biométricos ... Desde hace más de 30 años, la investigación enfocada a cómo representar objetos mediante grafos y el posterior cómputo de la distancia entre estas representaciones ha ocupado el trabajo de muchos investigadores. La definición de un modelo adecuado para medir la disimilitud entre dos de estas representaciones, es una cuestión clave en el campo del reconocimiento de patrones. A este problema se le ha llamado "Error-Tolerant Graph Matching". La "Graph Edit Distance" es una aproximación particular al problema del "Error-Tolerant Graph Matching " a partir del cómputo de la mínima distorsión necesaria para transformar un grafo en otro. El principal objetivo de esta tesis, es el de proponer un nuevo modelo para aprender automáticamente los parámetros de la "Graph Edit Distance" y definir diferentes estrategias activas de aprendizaje para añadir interactividad al problema. Esta tesis, también explora la definición de diferentes métricas para calcular la disimilitud entre sub-estructuras locales correspondientes a dos nodos y presenta un nuevo modelo basado en "metric-trees" de "Graph Class Prototypes" para guardar colecciones de grafos. Finalmente, se propone llevar el concepto de interactividad a otro dominio, el problema de relacionar los puntos entre dos imágenes para mejorar la precisión en el cálculo de la posición correlativa entre robots pertenecientes a una misma flota que trabaja de forma cooperativa.
Graphs are data types that can store structural information of objects and are commonly used to represent patterns that because of its nature require this peculiarity, as images, chemical or biological structures, networks, biometric patterns... For more than 30 years, researchers have been focused on how to represent objects through graphs and how to compute the distance between them. The definition of an adequate model for measure the dissimilarity between these representations is a key issue in pattern recognition. This is the Error-Tolerant Graph Matching problem. Graph Edit Distance is a particular approach to the Error-Tolerant Graph Matching problem by means of computing the minimum amount of distortion required to transform one graph into another. The main aim of this thesis is to propose a new model to automatically learn the parameters for Graph Edit Distance and to define different active learning strategies adding interactivity to the problem. Moreover, this thesis explores the definition of different metrics to estimate the dissimilarity between local substructures of two nodes and presents a new model based on metric-trees of Graph-Class Prototypes to store large collections of graphs. Finally, it is proposed to bring the interactivity to a different domain, the problem of matching the points of two images in order to improve the accuracy calculating the relative position between different robots of a fleet working cooperatively.

APA, Harvard, Vancouver, ISO, and other styles

31

Belhoul, Yacine. "Graph-based Ad Hoc Networks Topologies and Business Process Matching." Thesis, Lyon 1, 2013. http://www.theses.fr/2013LYO10202.

Full text

Abstract:

Un réseau mobile ad hoc (Mobile Ad hoc Network, MANET) est un réseau sans fil, formé dynamiquement par un ensemble d'utilisateurs équipés de terminaux mobiles, sans l'utilisation d'une infrastructure préexistante, ou d'une administration centralisée. Les équipements utilisés dans les MANETs sont limités par la capacité de la batterie, la puissance de calcul et la bande passante. Les utilisateurs des MANETs sont libres de se déplacer, ce qui induit à des topologies dynamiques dans le temps. Toutes ces contraintes ajoutent plus de challenges aux protocoles et services de communications afin de fonctionner dans les MANETs. L'évolution des réseaux de 4ème génération (4G) est appelée à intégrer les MANETs avec les autres types de réseaux afin d'étendre leurs portées. Nous nous sommes intéressés dans la première partie de cette thèse à quelques challenges connus dans les MANETs en proposant des solutions novatrices utilisant des propriétés intéressantes des topologies de graphes. Dans un premier temps, nous avons effectué une étude sur la prédiction de la mobilité afin de maintenir une topologie d'ensemble dominant connecté dans les MANETs. Nous avons proposé dans un autre travail comment construire des topologies de graphes ayant des propriétés globales en se basant seulement sur des informations locales des nœuds mobiles. Ces topologies servent comme overlay aux MANETs. Nous avons proposé des algorithmes distribués pour construire des alliances offensives et défensives globales minimales. Nous avons aussi défini des heuristiques pour ces algorithmes afin de réduire les tailles des alliances obtenues. La première partie de cette thèse est achevée par la proposition d'un framework pour la conception et l'analyse des protocoles de contrôle de topologie dans les MANETs. Nous avons identifié les points communs des algorithmes de contrôle de topologie conçus pour les réseaux mobiles ad hoc et nous avons enrichi le simulateur NS-2 avec un ensemble d'extensions pour supporter le contrôle de topologie
We are interested in this thesis to graph-based approaches to deal with some challenges in networking, namely, graph topologies of mobile ad hoc networks (MANETs) and process model matchmaking in large scale web service. We propose in the first part: (1) a generic mechanism using mobility information of nodes to maintain a graph topology of the network. We show particularly, how to use the prediction of future emplacements of nodes to maintain a connected dominating set of a given MANET. (2) distributed algorithms to construct minimal global offensive alliance and global defensive alliance sets in MANETs. We also introduce several heuristics to get a better approximation of the cardinality of the alliance sets which is a desirable property for practical considerations. (3) a framework to facilitate the design and evaluation of topology control protocols in MANETs. We propose in the framework, a common schema for topology control based on NS-2 simulator and inspired from the commonalities between the components of the topology control algorithms in MANETs. In the second part, we focus on process model matchmaking. We propose two graph-based solutions for process model inexact matching to deal with high computational time of existing work in the literature. In the first solution, we decompose the process models into their possible execution sequences. After, we propose generic graph techniques using string comparator metrics for process model matchmaking based on this decomposition. In order to get better optimization of the execution time and to deal with process model matching in large scale web services, the second solution combines a spectral graph matching with structural and semantic proposed approaches. This solution uses an eigen-decomposition projection technique that makes the runtime faster

APA, Harvard, Vancouver, ISO, and other styles

32

Zaslavskiy, Mikhail. "Graph matching and its application in computer vision and bioinformatics." Paris, ENMP, 2010. http://www.theses.fr/2010ENMP1659.

Full text

Abstract:

Le problème d'alignement de graphes, qui joue un rôle central dans différents domaines de la reconnaissance de formes, est l'un des plus grands défis dans le traitement de graphes. Nous proposons une méthode approximative pour l'alignement de graphes étiquetés et pondérés, basée sur la programmation convexe concave. Une application importante du problème d'alignement de graphes est l'alignement de réseaux d'interactions de protéines, qui joue un rôle central pour la recherche de voies de signalisation conservées dans l'évolution, de complexes protéiques conservés entre les espèces, et pour l'identification d'orthologues fonctionnels. Nous reformulons le problème d'alignement de réseaux d'interactions comme un problème d'alignement de graphes, et étudions comment les algorithmes existants d'alignement de graphes peuvent être utilisés pour le résoudre. Dans la formulation classique de problème d'alignement de graphes, seules les correspondances bijectives entre les noeuds de deux graphes sont considérées. Dans beaucoup d'applications, cependant, il est plus intéressant de considérer les correspondances entre des ensembles de noeuds. Nous proposons une nouvelle formulation de ce problème comme un problème d'optimisation discret, ainsi qu'un algorithme approximatif basé sur une relaxation continue. Nous présentons également deux résultats indépendents dans les domaines de la traduction automatique statistique et de la bio-informatique. Nous montrons d'une part comment le problème de la traduction statistique basé sur les phrases peut être reformulé comme un problème du voyageur de commerce. Nous proposons d'autre part une nouvelle mesure de similarité entre les sites de fixation de protéines, basée sur la comparaison 3D de nuages atomiques
The graph matching problem is among the most important challenges of graph processing, and plays a central role in various fields of pattern recognition. We propose an approximate method for labeled weighted graph matching, based on a convex-concave programming approach which can be applied to the matching of large sized graphs. This method allows to easily integrate information on graph label similarities into the optimization problem, and therefore to perform labeled weighted graph matching. One of the interesting applications of the graph matching problem is the alignment of protein-protein interaction networks. This problem is important when investigating evolutionary conserved pathways or protein complexes across species, and to help in the identification of functional orthologs through the detection of conserved interactions. We reformulate PPI alignment as a graph matching problem, and study how state-of-the-art graph matching algorithms can be used for this purpose. In the classical formulation of graph matching, only one-to-one correspondences are considered, which is not always appropriate. In many applications, it is more interesting to consider many-to-many correspondences between graph vertices. We propose a reformulation of the many-to-many graph matching problem as a discrete optimization problem and we propose an approximate algorithm based on a continuous relaxation. In this thesis, we also present two interesting results in statistical machine translation and bioinformatics. We show how the phrase-based statistical machine translation decoding problem can be reformulated as a Traveling Salesman Problem. We also propose a new protein binding pocket similarity measure based on a comparison of 3D atom clouds

APA, Harvard, Vancouver, ISO, and other styles

33

Madi, Kamel. "Inexact graph matching : application to 2D and 3D Pattern Recognition." Thesis, Lyon, 2016. http://www.theses.fr/2016LYSE1315/document.

Full text

Abstract:

Les Graphes sont des structures mathématiques puissantes constituant un outil de modélisation universel utilisé dans différents domaines de l'informatique, notamment dans le domaine de la reconnaissance de formes. L'appariement de graphes est l'opération principale dans le processus de la reconnaissance de formes à base de graphes. Dans ce contexte, trouver des solutions d'appariement de graphes, garantissant l'optimalité en termes de précision et de temps de calcul est un problème de recherche difficile et d'actualité. Dans cette thèse, nous nous intéressons à la résolution de ce problème dans deux domaines : la reconnaissance de formes 2D et 3D. Premièrement, nous considérons le problème d'appariement de graphes géométriques et ses applications sur la reconnaissance de formes 2D. Dance cette première partie, la reconnaissance des Kites (structures archéologiques) est l'application principale considérée. Nous proposons un "framework" complet basé sur les graphes pour la reconnaissance des Kites dans des images satellites. Dans ce contexte, nous proposons deux contributions. La première est la proposition d'un processus automatique d'extraction et de transformation de Kites a partir d'images réelles en graphes et un processus de génération aléatoire de graphes de Kites synthétiques. En utilisant ces deux processus, nous avons généré un benchmark de graphes de Kites (réels et synthétiques) structuré en 3 niveaux de bruit. La deuxième contribution de cette première partie, est la proposition d'un nouvel algorithme d'appariement pour les graphes géométriques et par conséquent pour les Kites. L'approche proposée combine les invariants de graphes au calcul de l'édition de distance géométrique. Deuxièmement, nous considérons le problème de reconnaissance des formes 3D ou nous nous intéressons à la reconnaissance d'objets déformables représentés par des graphes c.à.d. des tessellations de triangles. Nous proposons une décomposition des tessellations de triangles en un ensemble de sous structures que nous appelons triangle-étoiles. En se basant sur cette décomposition, nous proposons un nouvel algorithme d'appariement de graphes pour mesurer la distance entre les tessellations de triangles. L'algorithme proposé assure un nombre minimum de structures disjointes, offre une meilleure mesure de similarité en couvrant un voisinage plus large et utilise un ensemble de descripteurs qui sont invariants ou au moins tolérants aux déformations les plus courantes. Finalement, nous proposons une approche plus générale de l'appariement de graphes. Cette approche est fondée sur une nouvelle formalisation basée sur le problème de mariage stable. L'approche proposée est optimale en terme de temps d'exécution, c.à.d. la complexité est quadratique O(n2), et flexible en terme d'applicabilité (2D et 3D). Cette approche se base sur une décomposition en sous structures suivie par un appariement de ces structures en utilisant l'algorithme de mariage stable. L'analyse de la complexité des algorithmes proposés et l'ensemble des expérimentations menées sur les bases de graphes des Kites (réelle et synthétique) et d'autres bases de données standards (2D et 3D) attestent l'efficacité, la haute performance et la précision des approches proposées et montrent qu'elles sont extensibles et générales
Graphs are powerful mathematical modeling tools used in various fields of computer science, in particular, in Pattern Recognition. Graph matching is the main operation in Pattern Recognition using graph-based approach. Finding solutions to the problem of graph matching that ensure optimality in terms of accuracy and time complexity is a difficult research challenge and a topical issue. In this thesis, we investigate the resolution of this problem in two fields: 2D and 3D Pattern Recognition. Firstly, we address the problem of geometric graphs matching and its applications on 2D Pattern Recognition. Kite (archaeological structures) recognition in satellite images is the main application considered in this first part. We present a complete graph based framework for Kite recognition on satellite images. We propose mainly two contributions. The first one is an automatic process transforming Kites from real images into graphs and a process of generating randomly synthetic Kite graphs. This allowing to construct a benchmark of Kite graphs (real and synthetic) structured in different level of deformations. The second contribution in this part, is the proposition of a new graph similarity measure adapted to geometric graphs and consequently for Kite graphs. The proposed approach combines graph invariants with a geometric graph edit distance computation. Secondly, we address the problem of deformable 3D objects recognition, represented by graphs, i.e., triangular tessellations. We propose a new decomposition of triangular tessellations into a set of substructures that we call triangle-stars. Based on this new decomposition, we propose a new algorithm of graph matching to measure the distance between triangular tessellations. The proposed algorithm offers a better measure by assuring a minimum number of triangle-stars covering a larger neighbourhood, and uses a set of descriptors which are invariant or at least oblivious under most common deformations. Finally, we propose a more general graph matching approach founded on a new formalization based on the stable marriage problem. The proposed approach is optimal in term of execution time, i.e. the time complexity is quadratic O(n2) and flexible in term of applicability (2D and 3D). The analyze of the time complexity of the proposed algorithms and the extensive experiments conducted on Kite graph data sets (real and synthetic) and standard data sets (2D and 3D) attest the effectiveness, the high performance and accuracy of the proposed approaches and show that the proposed approaches are extensible and quite general

APA, Harvard, Vancouver, ISO, and other styles

34

Gutierrez, Munoz Alejandro. "Analysis of current flows in electrical networks for error-tolerant graph matching." [Tampa, Fla] : University of South Florida, 2008. http://purl.fcla.edu/usf/dc/et/SFE0002705.

Full text

APA, Harvard, Vancouver, ISO, and other styles

35

Ma, Fei, and feim@csem flinders edu au. "Registration of mass-like objects in sequential mammograms using graph matching." Flinders University. School of Computer Science, Engineering & Mathematics, 2008. http://catalogue.flinders.edu.au./local/adt/public/adt-SFU20090323.155040.

Full text

Abstract:

Sequential mammograms contain important information, such as changes of the breast or developments of the masses, for diagnosis of disease. Comparison of sequential mammograms plays an important part for radiologists in identifying malignant masses. However, currently computer-aided detection (CAD) programs can not use such information eciently. The diculties lie in the registration of sequential mammograms. Most of current methods register sequential mammograms based on control points and image transformations. For these methods to work, extraction and correspondence of the control points is essential. This thesis presents a new approach in registering mammograms. The proposed method registers mammograms by associating mass-like objects in sequential mammograms directly. The mass-like objects appear in the images of normal breasts as well as images of breast with cancer. When the mass-like objects in sequential mammograms are accurately associated, measurements of changes in mass-like objects over time become possible. This is an important way to distinguish mass-like objects associated with cancer from cysts or other benign objects. The proposed method is based on graph matching. It uses the internal structure of the breast represented by the spatial relation between the mass-like objects to establish a correspondence between the sequential mammograms. In this method, the mammogram is firstly segmented into separate components using an adaptive pyramid (AP) segmentation algorithm. A series of filters, based on the features of components, is then applied to the components to remove the undesired ones. The remaining components, the mass-like objects, are represented by a complete graph. The spatial relations between the remaining mass-like objects are expressed by fuzzy spatial relation representation and are associated to the edges of the graph as weights. Association of the mass-like objects of two sequential mammograms is realized by finding a common subgraph of the corresponding two graphs using the backtrack algorithm. The segmentation methods developed in the course of this work were tested on a separate problem in computer-aided detection of breast cancer, namely the automatic extraction of the pectoral muscle. The graph matching method was tested independently of the segmentation method on artificially distorted mammograms and the full process, including the segmentation and the graph matching, was evaluated on 95 temporal mammogram pairs. The present implementation indicates only a small improvement in cancer detection rates but also presents opportunities for a substantial development of the basic method in the future.

APA, Harvard, Vancouver, ISO, and other styles

36

Sanromà, Güell Gerard. "Graph matching using position coordinates and local features for image analysis." Doctoral thesis, Universitat Rovira i Virgili, 2012. http://hdl.handle.net/10803/79148.

Full text

Abstract:

Encontrar las correspondencias entre dos imágenes es un problema crucial en el campo de la visión por ordenador i el reconocimiento de patrones. Es relevante para un amplio rango de propósitos des de aplicaciones de reconocimiento de objetos en las áreas de biometría, análisis de documentos i análisis de formas hasta aplicaciones relacionadas con la geometría desde múltiples puntos de vista tales cómo la recuperación de la pose, estructura desde el movimiento y localización y mapeo. La mayoría de las técnicas existentes enfocan este problema o bien usando características locales en la imagen o bien usando métodos de registro de conjuntos de puntos (o bien una mezcla de ambos). En las primeras, un conjunto disperso de características es primeramente extraído de las imágenes y luego caracterizado en la forma de vectores descriptores usando evidencias locales de la imagen. Las características son asociadas según la similitud entre sus descriptores. En las segundas, los conjuntos de características son considerados cómo conjuntos de puntos los cuales son asociados usando técnicas de optimización no lineal. Estos son procedimientos iterativos que estiman los parámetros de correspondencia y de alineamiento en pasos alternados. Los grafos son representaciones que contemplan relaciones binarias entre las características. Tener en cuenta relaciones binarias al problema de la correspondencia a menudo lleva al llamado problema del emparejamiento de grafos. Existe cierta cantidad de métodos en la literatura destinados a encontrar soluciones aproximadas a diferentes instancias del problema de emparejamiento de grafos, que en la mayoría de casos es del tipo "NP-hard". El cuerpo de trabajo principal de esta tesis está dedicado a formular ambos problemas de asociación de características de imagen y registro de conjunto de puntos como instancias del problema de emparejamiento de grafos. En todos los casos proponemos algoritmos aproximados para solucionar estos problemas y nos comparamos con un número de métodos existentes pertenecientes a diferentes áreas como eliminadores de "outliers", métodos de registro de conjuntos de puntos y otros métodos de emparejamiento de grafos. Los experimentos muestran que en la mayoría de casos los métodos propuestos superan al resto. En ocasiones los métodos propuestos o bien comparten el mejor rendimiento con algún método competidor o bien obtienen resultados ligeramente peores. En estos casos, los métodos propuestos normalmente presentan tiempos computacionales inferiores.
Trobar les correspondències entre dues imatges és un problema crucial en el camp de la visió per ordinador i el reconeixement de patrons. És rellevant per un ampli ventall de propòsits des d’aplicacions de reconeixement d’objectes en les àrees de biometria, anàlisi de documents i anàlisi de formes fins aplicacions relacionades amb geometria des de múltiples punts de vista tals com recuperació de pose, estructura des del moviment i localització i mapeig. La majoria de les tècniques existents enfoquen aquest problema o bé usant característiques locals a la imatge o bé usant mètodes de registre de conjunts de punts (o bé una mescla d’ambdós). En les primeres, un conjunt dispers de característiques és primerament extret de les imatges i després caracteritzat en la forma de vectors descriptors usant evidències locals de la imatge. Les característiques son associades segons la similitud entre els seus descriptors. En les segones, els conjunts de característiques son considerats com conjunts de punts els quals son associats usant tècniques d’optimització no lineal. Aquests son procediments iteratius que estimen els paràmetres de correspondència i d’alineament en passos alternats. Els grafs son representacions que contemplen relacions binaries entre les característiques. Tenir en compte relacions binàries al problema de la correspondència sovint porta a l’anomenat problema de l’emparellament de grafs. Existeix certa quantitat de mètodes a la literatura destinats a trobar solucions aproximades a diferents instàncies del problema d’emparellament de grafs, el qual en la majoria de casos és del tipus “NP-hard”. Una part del nostre treball està dedicat a investigar els beneficis de les mesures de ``bins'' creuats per a la comparació de característiques locals de les imatges. La resta està dedicat a formular ambdós problemes d’associació de característiques d’imatge i registre de conjunt de punts com a instàncies del problema d’emparellament de grafs. En tots els casos proposem algoritmes aproximats per solucionar aquests problemes i ens comparem amb un nombre de mètodes existents pertanyents a diferents àrees com eliminadors d’“outliers”, mètodes de registre de conjunts de punts i altres mètodes d’emparellament de grafs. Els experiments mostren que en la majoria de casos els mètodes proposats superen a la resta. En ocasions els mètodes proposats o bé comparteixen el millor rendiment amb algun mètode competidor o bé obtenen resultats lleugerament pitjors. En aquests casos, els mètodes proposats normalment presenten temps computacionals inferiors.

APA, Harvard, Vancouver, ISO, and other styles

37

Saglik, Ozsarac Havva. "Fpga Implementation Of Graph Cut Method For Real Time Stereo Matching." Master's thesis, METU, 2010. http://etd.lib.metu.edu.tr/upload/12612556/index.pdf.

Full text

Abstract:

The present graph cut methods cannot be used directly for real time stereo matching applications because of their recursive structure. Graph cut method is modified to change its recursive structure so that making it suitable for real time FPGA (Field Programmable Gate Array) implementation. The modified method is firstly tested by MATLAB on several data sets, and the results are compared with those of previous studies. Although the disparity results of the modified method are not better than other methods&rsquo
, computation time performance is better. Secondly, the FPGA simulation is performed using real data sets. Finally, the modified method is implemented in FPGA with two PAL cameras at 25 Hz. The computation time of the implementation is 40 ms which is suitable for real time applications.

APA, Harvard, Vancouver, ISO, and other styles

38

MANZO, MARIO. "ATTRIBUTED RELATIONAL SIFT-BASED REGIONS GRAPH (ARSRG):DESCRIPTION, MATCHING AND APPLICATIONS." Doctoral thesis, Università degli Studi di Milano, 2014. http://hdl.handle.net/2434/233320.

Full text

Abstract:

Finding correspondences between images is a crucial activity in many overlapping fields of research, such as Image Retrieval and Pattern Recognition. Many existing techniques address this problem using local invariant image features, instead of color, shape and texture, that to some degree loose the large scale structure of the image. In this thesis, in order to account for spatial relations among the local invariant features and to improve the image representation, first a graph data structure is introduced, where local features are represented by nodes and spatial relations by edges; second an algorithm able to find matches between local invariant features, organized in graph structures, is built; third a mapping procedure from graph to vector space is proposed, in order to speed up the classification process. Effectiveness of the proposed framework is demonstrated through applications in image-based localization and art painting. The literature shows many approximate algorithms to solve these problems, so a comparison with the state of the art is performed in each step of the process. By using both local and spatial information, the proposed framework outperforms its competitors for the image correspondence problems.

APA, Harvard, Vancouver, ISO, and other styles

39

Ye, Jiacheng. "Computing Exact Bottleneck Distance on Random Point Sets." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98669.

Full text

Abstract:

Given a complete bipartite graph on two sets of points containing n points each, in a bottleneck matching problem, we want to find an one-to-one correspondence, also called a matching, that minimizes the length of its largest edge; the length of an edge is simply the Euclidean distance between its end-points. As an application, consider matching taxis to requests while minimizing the largest distance between any request to its matched taxi. The length of the largest edge (also called the bottleneck distance) has numerous applications in machine learning as well as topological data analysis. One can use the classical Hopcroft-Karp (HK-) Algorithm to find the bottleneck matching. In this thesis, we consider the case where A and B are points that are generated uniformly at random from a unit square. Instead of the classical HK-Algorithm, we implement and empirically analyze a new algorithm by Lahn and Raghvendra (Symposium on Computational Geometry, 2019). Our experiments show that our approach outperforms the HK-Algorithm based approach for computing bottleneck matching.
Master of Science
Consider the problem of matching taxis to an equal number of requests. While matching them, one objective is to minimize the largest distance between a request and its match. Finding such a matching is called the bottleneck matching problem. In addition, this optimization problem arises in topological data analysis as well as machine learning. In this thesis, I conduct an empirical analysis of a new algorithm, which is called the FAST-MATCH algorithm, to find the bottleneck matching. I find that, when a large input data is randomly generated from a unit square, the FAST-MATCH algorithm performs substantially faster than the classical methods

APA, Harvard, Vancouver, ISO, and other styles

40

Dunham, Brandan. "Mutually Exclusive Weighted Graph Matching Algorithm for Protein-Protein Interaction Network Alignment." University of Cincinnati / OhioLINK, 2016. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1470741019.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Demirci, Muhammed Fatih Shokoufandeh Ali. "Many-to-many feature matching for structural pattern recognition /." Philadelphia, Pa. : Drexel University, 2005. http://dspace.library.drexel.edu/handle/1860/656.

Full text

APA, Harvard, Vancouver, ISO, and other styles

42

Thoresen, Simon. "An efficient solution to inexact graph matching with application to computer vision." Doctoral thesis, Norwegian University of Science and Technology, Department of Computer and Information Science, 2007. http://urn.kb.se/resolve?urn=urn:nbn:no:ntnu:diva-1578.

Full text

Abstract:

Graph matching is considered the recognition step in computer vision. Our work uses attributed relation graphs (ARG’s) for image representation and analysis, a structural description that we enhance with the complete and coherent spatial knowledge of the source image.

In chapter 1 we reveal a trend where researchers are slowly incorporating more and more spatial knowledge into relational graphs. The ultimate realization of such knowledge in graphs is what we term a “spatially coherent attributed relational graph” whose connectivity is such that any degree of connectivity can be derived from any other. We argue that selective pruning or thresholding of connectivity in a graph is therefore the projection of a solution into a problem instance. This is our first contribution.

This trend degenerates most popular matching methods since these rely on graphs being sparsely connected, and typically collapse as connectivity increases.

In part 1 we introduce our second contribution; an inexact graph matcher whose performance increases with the connectivity of the graphs. Although the method is designed for our spatially coherent graphs, early research shows that it can even be applied to more traditional relational graphs as well. Our graph matcher extends the ideas of semilocal constraints to hold as global constraints. To solve intermediate instances of the assignment problem, we propose a very simple twopass method that performs with sufficient accuracy.

We present all runtimes in the number of comparisons that are performed on vertices and edges in a problem instance, since this measurement is separate from processor-time – a number biased by implementation skill, processor architecture and operating system. Our method runs by the least possible amount of vertex comparisons, and a tiny fraction of the upper-bound edge comparisons. It has a memory footprint that scales effortlessly with graph sizes.

Finally, in part 2 we present our third and last contribution; an object matcher capable of combining a set of graph matching results derived from multiple vision domains.

APA, Harvard, Vancouver, ISO, and other styles

43

Shaban, Khaled. "A Semantic Graph Model for Text Representation and Matching in Document Mining." Thesis, University of Waterloo, 2006. http://hdl.handle.net/10012/2860.

Full text

Abstract:

The explosive growth in the number of documents produced daily necessitates the development of effective alternatives to explore, analyze, and discover knowledge from documents. Document mining research work has emerged to devise automated means to discover and analyze useful information from documents. This work has been mainly concerned with constructing text representation models, developing distance measures to estimate similarities between documents, and utilizing that in mining processes such as document clustering, document classification, information retrieval, information filtering, and information extraction.

Conventional text representation methodologies consider documents as bags of words and ignore the meanings and ideas their authors want to convey. It is this deficiency that causes similarity measures to fail to perceive contextual similarity of text passages due to the variation of the words the passages contain, or at least perceive contextually dissimilar text passages as being similar because of the resemblance of words the passages have.

This thesis presents a new paradigm for mining documents by exploiting semantic information of their texts. A formal semantic representation of linguistic inputs is introduced and utilized to build a semantic representation scheme for documents. The representation scheme is constructed through accumulation of syntactic and semantic analysis outputs. A new distance measure is developed to determine the similarities between contents of documents. The measure is based on inexact matching of attributed trees. It involves the computation of all distinct similarity common sub-trees, and can be computed efficiently. It is believed that the proposed representation scheme along with the proposed similarity measure will enable more effective document mining processes.

The proposed techniques to mine documents were implemented as vital components in a mining system. A case study of semantic document clustering is presented to demonstrate the working and the efficacy of the framework. Experimental work is reported, and its results are presented and analyzed.

APA, Harvard, Vancouver, ISO, and other styles

44

Ta, Anh Phuong. "Inexact graph matching techniques : application to object detection and human action recognition." Lyon, INSA, 2010. http://theses.insa-lyon.fr/publication/2010ISAL0099/these.pdf.

Full text

Abstract:

Object detection and human action recognition are two active fields of research in computer vision, which have applications ranging from robotics and video surveillance, medical image analysis, human-computer interactions to content-based video annotation and retrieval. At this time, building such robust recognition systems still remain very challenging tasks, because of the variations in action/object classes, different possible viewpoints, as well as illumination changes, moving cameras, complex dynamic backgrounds and occlusions. In this thesis, we deal with object and activity recognition problems. Despite differences in the applications’ goals, the associated fundamental problems share numerous properties, for instance the necessity of handling non-rigid transformations. Describing a model object or a video by a set of local features, we formulate the recognition problem as a graph matching problem, where nodes represent local features, and edges represent spatial and/or spatio-temporal relationships between them. Inexact matching of valued graphs is a well known NP-hard problem, therefore we concentrated on finding approximate solutions. To this end, the graph matching problem is formulated as an energy minimization problem. Based on this energy function, we propose two different solutions for the two applications: object detection in images and activity recognition in video sequences. We also propose new features to improve the conventional Bag of words model, which is widely used in computer vision. Experiments on both standard datasets and our own datasets, demonstrate that our methods provide good results regarding the recent state-of-the-art in both domains
La détection d’objets et la reconnaissance des activités humaines sont les deux domaines actifs dans la vision par ordinateur, qui trouve des applications en robotique, vidéo surveillance, analyse des images médicales, interaction homme-machine, annotation et recherche de la vidéo par le contenue. Actuellement, il reste encore très difficile de construire de tels systèmes, en raison des variations des classes d’objets et d’actions, les différents points de vue, ainsi que des changements d’illumination, des mouvements de caméra, des fonds dynamiques et des occlusions. Dans cette thèse, nous traitons le problème de la détection d’objet et d’activités dans la vidéo. Malgré ses différences de buts, les problèmes fondamentaux associés partagent de nombreuses propriétés, par exemple la nécessité de manipuler des transformations non-ridiges. En décrivant un modèle d’objet ou une vidéo par un ensemble des caractéristiques locales, nous formulons le problème de reconnaissance comme celui d’une mise en correspondance de graphes, dont les nœuds représentent les caractéristiques locales, et les arrêtes représentent les relations que l’on veut vérifier entre ces caractéristiques. Le problème de mise en correspondance inexacte de graphes est connu comme NP-difficile, nous avons donc porté notre effort sur des solutions approchées. Pour cela, le problème est transformé en problème d’optimisation d’une fonction d’énergie, qui contient un terme en rapport avec la distance entre les descripteurs locaux et d’autres termes en rapport avec les relations spatiales (ou/et temporelles) entre eux. Basé sur cette énergie, deux différentes solutions ont été proposées et validées pour les deux applications ciblées: la reconnaissance d’objets à partir d’images et la reconnaissance des activités dans la vidéo. En plus, nous avons également proposé un nouveaux descripteur pour améliorer les modèles de Sac-de-mots, qui sont largement utilisé dans la vision par ordinateur. Nos expérimentations sur deux bases standards, ainsi que sur nos bases démontrent que les méthodes proposées donnent de bons résultats en comparant avec l’état de l’art dans ces deux domaines

APA, Harvard, Vancouver, ISO, and other styles

45

Rodenas, Pico David. "Algorithms acceleration of pattern-matching in multi-core architectures." Doctoral thesis, Universitat Rovira i Virgili, 2011. http://hdl.handle.net/10803/37361.

Full text

Abstract:

L'objectiu d'aquesta tesis es crear o adaptar models de programació per a fer els processadors multi-core accessibles per a la majoria de programadors. Aquest objectiu inclou la possibilitat de reusar els algoritmes existents, la capacitat de depuració, I la capacitat d'introduir els canvis de forma incremental. Contrastem les solucions proposades en diversos tipus de multi-core, incloent sistemes homogenis i heterogenis, i sistemes de memòria compartida i memòria distribuïda. A més a més contribuïm exposant algorismes i programes reals i ensenyant com aquests es poden ser usat per aplicacions en temps quasi real.
The aim of this thesis is to create or adapt a programming model in order to make multi-core processors accessible by almost every programmer. This objective includes existing codes and algorithms reuse, debuggability, and the capacity to introduce changes incrementally. We face multi-cores with many architectures including homogeneity versus heterogeneity and shared-memory versus distributed-memory. We also contribute by exposing real algorithms and programs and showing how some of them can be used for quasi realtime applications.

APA, Harvard, Vancouver, ISO, and other styles

46

Myers, Richard Oliver. "Genetic algorithms for ambiguous labelling problems." Thesis, University of York, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.310985.

Full text

APA, Harvard, Vancouver, ISO, and other styles

47

Koushaeian, Reza. "An Ontology And Conceptual Graph Based Best Matching Algorithm For Context-aware Applications." Master's thesis, METU, 2011. http://etd.lib.metu.edu.tr/upload/12613216/index.pdf.

Full text

Abstract:

Context-aware computing is based on using knowledge about the current context. Interpretation of current context to an understandable knowledge is carried out by reasoning over context and in some cases by matching the current context with the desired context. In this thesis we concentrated on context matching issue in context-aware computing domain. Context matching can be done in various ways like it is done in other matching processes. Our matching approach is best matching in order to generate granular similarity results and not to be limited to Boolean values. We decided to use Ontology as the encoded domain knowledge for our matching method. Context matching method is related to the method that we represent context. We selected conceptual graphs to represent the context. We proposed a generic algorithm for context matching based on the ontological information that benefit from the conceptual graph theory and its advantages.

APA, Harvard, Vancouver, ISO, and other styles

48

DUARTE, ALEXANDRE ROCHA. "NEW HEURISTICS AND AN INTEGER PROGRAMMING APPROACH TO AN INEXACT GRAPH MATCHING PROBLEM." PONTIFÍCIA UNIVERSIDADE CATÓLICA DO RIO DE JANEIRO, 2004. http://www.maxwell.vrac.puc-rio.br/Busca_etds.php?strSecao=resultado&nrSeq=4715@1.

Full text

Abstract:

COORDENAÇÃO DE APERFEIÇOAMENTO DO PESSOAL DE ENSINO SUPERIOR
Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata.
This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.

APA, Harvard, Vancouver, ISO, and other styles

49

Li, Shirong. "A FRAMEWORK FOR SAMPLING PATTERN OCCURRENCES IN A HUGE GRAPH." Cleveland, Ohio : Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1269979693.

Full text

Abstract:

Thesis (Master of Sciences)--Case Western Reserve University, 2010
Department of EECS - Computer and Information Sciences Title from PDF (viewed on 2010-05-25) Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center

APA, Harvard, Vancouver, ISO, and other styles

50

Vasilyeva, Elena. "Why-Query Support in Graph Databases." Doctoral thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2017. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-221730.

Full text

Abstract:

In the last few decades, database management systems became powerful tools for storing large amount of data and executing complex queries over them. In addition to extended functionality, novel types of databases appear like triple stores, distributed databases, etc. Graph databases implementing the property-graph model belong to this development branch and provide a new way for storing and processing data in the form of a graph with nodes representing some entities and edges describing connections between them. This consideration makes them suitable for keeping data without a rigid schema for use cases like social-network processing or data integration. In addition to a flexible storage, graph databases provide new querying possibilities in the form of path queries, detection of connected components, pattern matching, etc. However, the schema flexibility and graph queries come with additional costs. With limited knowledge about data and little experience in constructing the complex queries, users can create such ones, which deliver unexpected results. Forced to debug queries manually and overwhelmed by the amount of query constraints, users can get frustrated by using graph databases. What is really needed, is to improve usability of graph databases by providing debugging and explaining functionality for such situations. We have to assist users in the discovery of what were the reasons of unexpected results and what can be done in order to fix them. The unexpectedness of result sets can be expressed in terms of their size or content. In the first case, users have to solve the empty-answer, too-many-, or too-few-answers problems. In the second case, users care about the result content and miss some expected answers or wonder about presence of some unexpected ones. Considering the typical problems of receiving no or too many results by querying graph databases, in this thesis we focus on investigating the problems of the first group, whose solutions are usually represented by why-empty, why-so-few, and why-so-many queries. Our objective is to extend graph databases with debugging functionality in the form of why-queries for unexpected query results on the example of pattern matching queries, which are one of general graph-query types. We present a comprehensive analysis of existing debugging tools in the state-of-the-art research and identify their common properties. From them, we formulate the following features of why-queries, which we discuss in this thesis, namely: holistic support of different cardinality-based problems, explanation of unexpected results and query reformulation, comprehensive analysis of explanations, and non-intrusive user integration. To support different cardinality-based problems, we develop methods for explaining no, too few, and too many results. To cover different kinds of explanations, we present two types: subgraph- and modification-based explanations. The first type identifies the reasons of unexpectedness in terms of query subgraphs and delivers differential graphs as answers. The second one reformulates queries in such a way that they produce better results. Considering graph queries to be complex structures with multiple constraints, we investigate different ways of generating explanations starting from the most general one that considers only a query topology through coarse-grained rewriting up to fine-grained modification that allows fine changes of predicates and topology. To provide a comprehensive analysis of explanations, we propose to compare them on three levels including a syntactic description, a content, and a size of a result set. In order to deliver user-aware explanations, we discuss two models for non-intrusive user integration in the generation process. With the techniques proposed in this thesis, we are able to provide fundamentals for debugging of pattern-matching queries, which deliver no, too few, or too many results, in graph databases implementing the property-graph model.

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic 'Graph matching'

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