On the Evaluation of Reachability and Sub-pattern Recognition Queries in Very Large Graph Databases

点击翻译按钮获取中文摘要

With the advent of web technology, numerous new applications have emerged, such as social networks, semantic web, and web mining, which need to work with graph-like data due to its expressive power to handle complex relationships among objects. In addition, many other research areas need to model their data as graphs. Instances include trace of infectious diseases, computer vision, knowledge discovery, biological networks, cheminformatics, electrical power grids, and network traffic, just to name a few. To query data graphs, two kinds of queries are being widely used: - Reachability queries, asking whether there exists a path from one node to another. - Graph pattern queries, to find all subgraphs that are isomorphic to a pattern graph. The reachability query is deemed to be one of the most basic building blocks for many advanced graph operations. As an example, consider a network that represents locations, or people as nodes and disease transmission, such as COVID-19, SARS as edges. One may want to know whether a certain disease is spread from a city or a person to the others. As another example, in biological networks, nodes are either molecules, or reactions, or physical interaction of living cells, and edges are interactions among them. We may want to find all genes whose expressions are directly or indirectly influenced by a certain molecule. In addition, in the graph theory, the subgraph isomorphism (recognition) is to check sub-structure identity. Two graphs G(V, E) and G'(V', E') are isomorphic if there exists a bijection f, from V to V', such that (u, v) is in E if (f(u), f(v)) is in E'. It is an NP-complete problem. For this reason, different variants of graph matchings have been suggested, which can be evaluated in polynomial time but quite useful in practice. For example, we can allow an edge in a pattern to match a path in a target, or define a pattern as a constraint to find all those subgraphs satisfying the constraint. Further, in some emerging applications, such as social networks, edges in a graph are typically typed, denoting various relationships such as marriage, friendship, co-work, advice, and so on. It is another important difference from the traditional graph theory, posing new challenges in seeking for efficient algorithms to evaluate reachability queries and graph pattern queries. We have worked on the reachability queries and sub-graph recognition on both typed and untyped graphs for a long time, and developed efficient algorithms with better theoretic time complexity than the existing strategies. All our research results have been published in some prestiges venues, such as ACM Transactions on Database Systems, IEEE Transactions on Knowledge and Data Engineering, Journal of Super Computing, and Intl. Conf. Data Enginerring. The goal of this project is to build a software system to evaluate reachability queries and graph pattern queries on both untyped and typed graphs with our algorithms being utilized.