6-Transitive closures and triangle consistency checking:a new way to evaluate graph pattern queries in large graph databases

摘要

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 queries, reachability verification, pattern matching, and so on. Among them, the graph pattern matching is to find all matches in a data graphGfor a given pattern graphQand is more general and flexible compared with other problems mentioned above. In this paper, we address a kind of graph matching, the so-calledgraph matching with delta, by which an edge inQis allowed to match a path of length = delta inG. In order to reduce the search space when exploringGto find matches, we propose a new index structure and a novel pruning technique to eliminate a lot of unqualified vertices before join operations are carried out. Extensive experiments have been conducted, which show that our approach makes great improvements in running time compared to existing ones.