On the Evaluation of Pattern Match Queries in Large Graph Databases

Abstract

Recently, graph databases have been received much attention in the research community due to their extensive applications in practice, such as social networks, biological networks and World Wide Web, which bring forth a lot of challenging data management problems including subgraph search, shortest-path query, reachability verification, pattern matching, and so on. Among them, the graph pattern matching is to find all matches in a data graph 𝐺 for a given pattern graph 𝑄 and is more general and flexible than other problems mentioned above. In this thesis, we address a kind of graph matching, the so-called pattern matching with δ, by which an edge in 𝑄 is allowed to match a path of length ≤ δ in 𝐺. In order to reduce the search space when exploring 𝐺 to find matches, we propose a novel pruning algorithm to eliminate all unqualified vertices. We also propose a strategy to speed up the distance-based join over two lists of vertices. Extensive experiments have been conducted, which show that our approach makes great improvements in running time compared to existing ones.