Show simple item record

dc.contributor.advisorFan, Wenfei
dc.contributor.advisorGeerts, Floris
dc.contributor.authorWu, Yinghui
dc.date.accessioned2011-08-01T10:20:46Z
dc.date.available2011-08-01T10:20:46Z
dc.date.issued2011-06-30
dc.identifier.urihttp://hdl.handle.net/1842/5022
dc.description.abstractAmong 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.en
dc.contributor.sponsorEngineering and Physical Sciences Research Council (EPSRC)en
dc.language.isoenen
dc.publisherThe University of Edinburghen
dc.relation.hasversionTing Deng, Wenfei Fan, Leonid Libkin, and Yinghui Wu. On the aggregation problem for synthesized web services. In ICDT, 2010.en
dc.relation.hasversionWenfei Fan, Jianzhong Li, Shuai Ma, Tang Nan, Yinghui Wu, and Yunpeng Wu. Graph pattern matching: From intractable to polynomial time. PVLDB, 3, 2010.en
dc.relation.hasversionWenfei Fan, Jianzhong Li, Shuai Ma, Nan Tang, Yinghui Wu, and Yunpeng Wu. Graph pattern matching: From intractability to polynomial time. In PVLDB, 2010.en
dc.relation.hasversionWenfei Fan, Jianzhong Li, Shuai Ma, Hongzhi Wang, and Yinghui Wu. Graph homomorphism revisited for graph matching. In PVLDB, 2010.en
dc.relation.hasversionWenfei Fan, Jianzhong Li, Shuai Ma, Nan Tang, and YinghuiWu. Adding regular expressions to graph reachability and pattern queries. In ICDE, 2011.en
dc.subjectgraph matchingen
dc.subjecthomomorphismen
dc.subjectsimulationen
dc.titleExtending graph homomorphism and simulation for real life graph matchingen
dc.typeThesis or Dissertationen
dc.type.qualificationlevelDoctoralen
dc.type.qualificationnamePhD Doctor of Philosophyen


Files in this item

This item appears in the following Collection(s)

Show simple item record