Abstract: |
Attributed graphs are powerful data structures for the representation of complex objects. In a graph-based representation, vertices and their attributes describe objects (or part of objects) while edges represent interrelationships between the objects. Due to the inherent genericity of graph-based representations, and thanks to the improvement of computer
capacities, structural representations have become more and more popular in the field of Pattern Recognition (PR). In this thesis, we tackle two important graph-based problems for PR: Graph Matching and Graph Indexing. The comparison between two objects is a crucial operation in PR. Representing objects by graphs turns the problem of object comparison into graph
matching where correspondences between nodes and edges of two graphs have to be found. Moreover, graph-based indices are important so that a graph query can be retrieved from a large database via such indices, such a problem is referred to as graph indexing. The complexity of both graph matching and graph indexing is generally stated to be NP-COMPLETE or NP-hard.
Coming up with a graph matching algorithm that can scale up to match graphs involved in PR tasks is a great challenge. Among the graph matching methods dedicated to PR problems, the Graph Edit Distance (GED) is of great interest. Over the last decade, GED has been applied to a wide range of specific applications from molecule recognition to image classification.
In this report, we present the first part of the thesis. We tackle GED, shed light on the importance of having exact solutions rather than approximate ones and come up with a distributed GED where the search tree is decomposed into smaller trees which are solved independently and in a complete distributed manner. In the second part of the thesis,
we aim at proposing new distributed graph-indexing approaches that aim at retrieving a graph from a large graph-based index as fast as possible. Graph indexing will be reported as a perspective of this work. |