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

超大型图数据库中的可达性评估和子模式识别查询

• 批准号: RGPIN-2022-02971
• 负责人: Chen, Yangjun
• 金额: $ 2.11万
• 依托单位: University of Winnipeg
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=743623
• 关键词: Evaluation; Reachability; Sub; pattern; Recognition

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.

随着web技术的出现，出现了许多新的应用程序，如社交网络、语义网和web挖掘，它们需要处理类图数据，因为它具有处理对象之间复杂关系的表达能力。此外，许多其他研究领域需要将其数据建模为图形。例子包括传染病的追踪、计算机视觉、知识发现、生物网络、化学信息学、电网和网络流量，仅举几例。为了查询数据图，有两种查询被广泛使用：—可达性查询，询问是否存在从一个节点到另一个节点的路径。-图形模式查询，查找与模式图同构的所有子图。可达性查询被认为是许多高级图操作的最基本的构建块之一。例如，考虑一个以位置或人员为节点，以疾病传播（如COVID-19、SARS）为边缘的网络。人们可能想知道某种疾病是否从一个城市或一个人传播到其他城市。又如，在生物网络中，节点或者是分子，或者是反应，或者是活细胞之间的物理相互作用，而边缘则是它们之间的相互作用。我们可能想要找到所有的基因，它们的表达直接或间接地受到某种分子的影响。此外，在图论中，子图同构（识别）是为了检验子结构的同一性。两个图G（V， E）和G‘（V‘， E’）是同构的，如果存在一个从V到V’的双射f，使得（u， V）在E中，如果(f（u), f(V)）在E'中。这是一个np完全问题。由于这个原因，已经提出了不同的图匹配变体，这些变体可以在多项式时间内评估，但在实践中非常有用。例如，我们可以允许模式中的一条边匹配目标中的一条路径，或者将模式定义为一个约束，以找到满足该约束的所有子图。此外，在一些新兴的应用程序（如社交网络）中，图中的边通常是有类型的，表示各种关系，如婚姻、友谊、合作、建议等。这是与传统图论的另一个重要区别，为寻找有效的算法来评估可达性查询和图模式查询提出了新的挑战。我们对类型化和非类型化图的可达性查询和子图识别进行了长期的研究，并开发了比现有策略具有更好理论时间复杂度的高效算法。我们所有的研究成果都发表在ACM Transactions on Database Systems、IEEE Transactions on Knowledge and Data Engineering、Journal of Super Computing、Intl等权威期刊上。Conf.数据工程这个项目的目标是构建一个软件系统，在使用我们的算法的情况下，评估非类型化和类型化图上的可达性查询和图模式查询。