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和Web挖掘，这些应用需要处理图状数据，因为它具有处理对象之间复杂关系的表达能力。此外，许多其他研究领域需要将其数据建模为图形。例子包括传染病的痕迹、计算机视觉、知识发现、生物网络、化学信息学、电网和网络交通，仅举几例。为了查询数据图，有两种查询被广泛使用：-可达性查询，询问是否存在从一个节点到另一个节点的路径。-图形模式查询，查找与模式图同构的所有子图。可达性查询被认为是许多高级图形操作的最基本的构建块之一。例如，假设一个网络将位置表示为节点，或将人表示为节点，将疾病传播表示为边，如新冠肺炎、SARS。人们可能想知道某种疾病是否从一个城市或一个人传播到其他城市或人。又如，在生物网络中，节点要么是分子，要么是反应，要么是活细胞的物理相互作用，而边是它们之间的相互作用。我们可能想要找出其表达受到某一特定分子直接或间接影响的所有基因。另外，在图论中，子图同构(识别)是为了验证子结构同一性。两个图G(V，E)和G‘(V’，E‘)同构，如果存在从V到V’的双射f，使得(u，v)在E中如果(f(U)，f(V))在E‘中。这是一个NP完全问题。为此，已经提出了图匹配的不同变体，它们可以在多项式时间内计算，但在实践中非常有用。例如，我们可以允许模式中的边与目标中的路径匹配，或者将模式定义为约束，以找到满足该约束的所有子图。此外，在一些新兴的应用中，如社交网络，图中的边通常是类型化的，表示各种关系，如婚姻、友谊、合作、建议等。这是与传统图论的另一个重要区别，对寻找有效的算法来评估可达性查询和图模式查询提出了新的挑战。我们对类型化图和非类型化图的可达性查询和子图识别进行了长期的研究，并提出了比现有策略更好的理论时间复杂度的高效算法。我们所有的研究成果都发表在一些有声望的论坛上，如ACM数据库系统会刊，IEEE知识和数据工程会刊，超级计算杂志和国际贸易协会。电话会议数据引擎。这个项目的目标是构建一个软件系统，利用我们的算法来评估非类型化图和类型化图上的可达性查询和图模式查询。