检索结果-内蒙古大学图书馆

graph pattern matching: Capturing Bisimilar Subgraph

INTERNATIONAL JOURNAL OF pattern RECOGNITION AND ARTIFICIAL INTELLIGENCE 2021年第3期35卷

作者： Qiao, Rui Feng, Ke He, Heng Zhong, Xiaolei Wuhan Univ Sci & Technol Coll Comp Sci & Technol Wuhan Peoples R China Hubei Prov Key Lab Intelligent Informat Proc & Re Wuhan Peoples R China Yunnan Univ Kunming Yunnan Peoples R China

graph pattern matching that aims to seek out answer graphs in a data graph matching a provided graph, plays a fundamental role as a part of graph search for graph databases. "matching" indicates that the two graphs are correlated, such as bisimulation, isomorphism, simulation, etc. The strictness of bisimulation is between simulation and isomorphism. Seldom work has been done to search for bisimulation subgraphs. This research focuses on the problem. The symbol is introduced to fundamental modal logic language, thereby yielding ML+ language;the symbols square is added for forming ML+ formulas. Then conclusions about graph bisimulations are shown. Subsequently, a theorem with detailed proof is presented, stating that ML+ formulas characterize finite directed graphs modulo bisimulation. According to the conclusions and theorem, algorithms for finding subgraphs are proposed. After dividing the query graph, the match graphs undergo the characterization using ML+ formulas. In the data graphs, by model checking the formulas, the answer graphs exhibiting bisimilarity to the match graphs are able to be captured.

关键词： graph pattern matching bisimulation model checking graph search graph database

来源：评论

学校读者我要写书评

暂无评论

graph pattern matching through Model Checking 8

Graph Pattern Matching through Model Checking

引用

8th International Conference on Database Theory and Application (DTA)

作者： Qiao, Rui Zhong, Xiaolei Zhang, Ling He, Heng Wuhan Univ Sci & Technol Coll Comp Sci & Technol Hubei Prov Key Lab Intelligent Informat Proc & Re Wuhan Peoples R China Huazhong Univ Sci Sch Software Wuhan Peoples R China Wuhan Univ Sci & Technol Coll Management Wuhan Peoples R China

ISBN: (纸本)9781467398497

graph pattern matching is a hot spot in the big data era, which is to find answer graphs matching a given query graph in a data graph of graph databases. "matching" means two graphs satisfy some relation, such as isomorphism, simulation, bisimulation, etc. Since there are seldom algorithms for the subgraph bisimulation, our work commits to solve the graph pattern matching problem involving bisimulation relations through the model checking technology. We characterize query graphs by modal formulas. By model checking the formulas in the data graphs, the answer graphs bisimilar to the query graphs can be discovered. We add * to basic modal logic language resulting in ML + * language, and add r* to form ML + * formulas. Then a theorem which states that ML + * formulas characterize finite directed graphs modulo bisimulation is put forward. Furthermore, we list steps to find answer graphs bisimilar to a query graph.

关键词： graph pattern matching Modal formula Bisimulation Model checking Query processing graph database

来源：评论

学校读者我要写书评

暂无评论

graph pattern matching: A Brief Survey of Challenges and Research Directions 3

Graph Pattern Matching: A Brief Survey of Challenges and Res...

引用

3rd International Conference on Computing for Sustainable Global Development (INDIACom)

作者： Singh, Komal Singh, Vikram Natl Inst Technol Kurukshetra Haryana India

ISBN: (纸本)9789380544199

Due to tremendous intensification of Internet, most of the data is archived and analyzed in graph-structured database. graph Database is a collection of operational data objects, mapped into huge labeled graph or a set of labeled directed graphs. In recent years, modeling data in graph structure becomes evident and effective for processing in some of the prominent application area like social analytics etc. graph databases are mapped into data graphs for further computing or processing. graphs are one of the dominant data modeling tool used in many application areas. Hence, there is a demand for proficient querying techniques on such large data graphs. The user query is mapped into pattern graph, which is constructed by connecting nodes based on links/relationships required by user. The primary objective of graph pattern matching (GPM) is to determine all the candidates matching to a pattern query in a large data graph. This survey paper discusses various graph pattern matching approaches, used by researchers in recent year for query processing. Further, we also highlight the various challenges imposed by modern day computing and possible future research directions in query processing using graph pattern matching.

关键词： Big Data Analytics graph Data graph pattern matching graph Mining Query Processing

来源：评论

学校读者我要写书评

暂无评论

graph pattern matching Based Intelligent Operation and Maintenance Method for Cloud Resource Operation 8

Graph Pattern Matching Based Intelligent Operation and Maint...

引用

8th International Conference on Data Science in Cyberspace, DSC 2023

作者： Qiao, Lin Qu, Ruiting Song, Qing Lyu, Xuming Wang, Lixia Qi, Jun State Grid Liaoning Electronic Power Company China Shenyang China State Grid Liaoning Electric Power Company China Information and Communication Branch Shenyang China

ISBN: (纸本)9798350331035

In recent years, cloud computing technology has been widely used in various industries. The cloud platform architecture has thoroughly realized high scalability, high stability and low maintenance cost. However, along with the development of geometric growth in the number of micro-applications, cloud platform O&M such as abnormal monitoring and fault location of large-scale micro-services is facing new difficulties and challenges. Traditional cloud platform operation and maintenance work mainly relies on human experience to analyze a large number of indicators to determine whether there is a failure, which is very inefficient and relies heavily on expert opinions. To address the above issues, this paper applies graph pattern matching technology to the cloud platform. In the face of metrics monitoring data, link topology data, log data, and cloud resource data of the whole life cycle of micro-services, we design graph patterns based on existing cloud resource data, and then look for them in the existing fault graph to determine whether faults occur and achieve intelligent operation and maintenance of cloud resource operation. Experimental results on four datasets show that our approach is more effective than traditional methods. © 2023 IEEE.

关键词： Cloud Resources Fault detection graph pattern matching Intelligent Operation and Maintenance

来源：评论

学校读者我要写书评

暂无评论

graph pattern matching on social network analysis

Graph pattern matching on social network analysis

引用

作者： Wang, Xin The University of Edinburgh

学位级别：master

graph pattern matching is fundamental to social network analysis. Its effectiveness for identifying social communities and social positions, making recommendations and so on has been repeatedly demonstrated. However, the social network analysis raises new challenges to graph pattern matching. As real-life social graphs are typically large, it is often prohibitively expensive to conduct graph pattern matching over such large graphs, e.g., NP-complete for subgraph isomorphism, cubic time for bounded simulation, and quadratic time for simulation. These hinder the applicability of graph pattern matching on social network analysis. In response to these challenges, the thesis presents a series of effective techniques for querying large, dynamic, and distributively stored social networks. First of all, we propose a notion of query preserving graph compression, to compress large social graphs relative to a class Q of queries. We then develop both batch and incremental compression strategies for two commonly used pattern queries. Via both theoretical analysis and experimental studies, we show that (1) using compressed graphs Gr benefits graph pattern matching dramatically; and (2) the computation of Gr as well as its maintenance can be processed efficiently. Secondly, we investigate the distributed graph pattern matching problem, and explore parallel computation for graph pattern matching. We show that our techniques possess following performance guarantees: (1) each site is visited only once; (2) the total network traffic is independent of the size of G; and (3) the response time is decided by the size of largest fragment of G rather than the size of entire G. Furthermore, we show how these distributed algorithms can be implemented in the MapReduce framework. Thirdly, we study the problem of answering graph pattern matching using views since view based techniques have proven an effective technique for speeding up query evaluation. We propose a notion of pattern containment

关键词： graph pattern matching social network

来源：评论

学校读者我要写书评

暂无评论

Strong Social graph Based Trust-Oriented graph pattern matching With Multiple Constraints

引用

IEEE TRANSACTIONS ON EMERGING TOPICS IN COMPUTATIONAL INTELLIGENCE 2020年第5期4卷 675-685页

作者： Liu, Guanfeng Wang, Yurong Zheng, Bolong Li, Zhixu Zheng, Kai Macquarie Univ Sydney NSW 2109 Australia Soochow Univ Suzhou 215168 Peoples R China Huazhong Univ Sci & Technol Wuhan 430079 Peoples R China Univ Elect Sci & Technol Chengdu 610051 Peoples R China

Online social network is popular and graph pattern matching (GPM) has been significant in many social network based applications, such as experts finding and social position detection. However, the existing GPM methods do not consider the multiple constraints of the social contexts in GPM, which are commonly found in various applications, or they do not consider the changes of graph structure in the index maintenance of GPM, leading to low efficiency. In this paper, we first propose a multi-constrained simulation based on the hounded graph simulation, and propose a multi-constrained graph pattern matching (MC-GPM) problem. To improve the efficiency of MC-GPM in large social graphs, we propose a new concept, strong social graph (SSG), that contains the users who have strong social connections. Then, we propose an SSG-index method to index the reachability, the graph patterns, and the social contexts of social graphs. Finally, we propose an incremental algorithm to maintain the SSG-index, which can greatly save the execution time when faced with the change of the structures of SSGs. Moreover, by combining SSC-index, we develop a heuristic algorithm, called SSG-MGPM, to identify MC-GPM results effectively and efficiently. An empirical study over five real-world social graphs has demonstrated the superiority of our approach in terms of efficiency and effectiveness.

关键词： Trust social network graph pattern matching

来源：评论

学校读者我要写书评

暂无评论

Distributed Partial Simulation for graph pattern matching

引用

COMPUTER JOURNAL 2024年第1期67卷 110-126页

作者： Aouar, Aissam Yahiaoui, Said Sadeg, Lamia Nouali-Taboudjemat, Nadia Beghdad Bey, Kadda Ecole Mil Polytech BP 17 Algiers 16111 Algeria CERIST Res Ctr Sci & Tech Informat Algiers 16030 Algeria

pattern matching in big graphs is important for different modern applications. Recently, this problem was defined in terms of multiple extensions of graph simulation, to reduce complexity and capture more meaningful results. These results were achieved through the relaxation of commonly used constraint in subgraph isomorphism pattern matching. Nevertheless, these graph simulation variant models are still too strict to provide results in many cases, especially when analyzed graphs contain anomalies and incomplete information. To deal with this issue, we introduce a new graph pattern matching (GPM) method, called partial simulation, capable of retrieving matches despite missing parts of the pattern graph, such as vertices and/or edges. Furthermore, considering the number and inequality of the outputs, we define a relevance function to compute a value expressing how each match vertex respects the pattern graph. Similarly, we define partial dual simulation GPM that returns vertices that satisfy a part of the dual simulation constraints and assigns a relevance value to them. Additionally, we provide distributed scalable algorithms to evaluate the proposed partial simulation methods based on the distributed vertex-centric programming paradigm. Finally, our experiments on real-world data graphs demonstrate the effectiveness of the proposed models and the efficiency of their associated algorithms.

关键词： big graphs graph pattern matching graph simulation distributed computing vertex-centric programming

来源：评论

学校读者我要写书评

暂无评论

Hybrid search plan generation for generalized graph pattern matching

引用

JOURNAL OF LOGICAL AND ALGEBRAIC METHODS IN PROGRAMMING 2020年 114卷

作者： Barkowsky, Matthias Giese, Holger Univ Potsdam Hasso Plattner Inst Prof Dr Helmert Str 2-3 D-14482 Potsdam Germany

In recent years, the increased interest in application areas such as social networks has resulted in a rising popularity of graph-based approaches for storing and processing large amounts of interconnected data. To extract useful information from the growing network structures, efficient querying techniques are required. In this paper, we propose an approach for graph pattern matching that allows a uniform handling of arbitrary constraints over the query vertices. Our technique builds on a previously introduced matching algorithm, which takes concrete host graph information into account to dynamically adapt the employed search plan during query execution. The dynamic algorithm is combined with an existing static approach for search plan generation, resulting in a hybrid technique which we further extend by a more sophisticated handling of filtering effects caused by constraint checks. We evaluate the presented concepts empirically based on an implementation for our graph pattern matching tool, the Story Diagram Interpreter, with queries and data provided by the LDBC Social Network Benchmark. Our results suggest that the hybrid technique may improve search efficiency in several cases, and rarely reduces efficiency. (C) 2020 Elsevier Inc. All rights reserved.

关键词： graph pattern matching Search plan generation

来源：评论

学校读者我要写书评

暂无评论

MCS-GPM: Multi-Constrained Simulation Based graph pattern matching in Contextual Social graphs

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2018年第6期30卷 1050-1064页

作者： Liu, Guanfeng Liu, Yi Zheng, Kai Liu, An Li, Zhixu Wang, Yang Zhou, Xiaofang Soochow Univ Sch Comp Sci & Technol Suzhou 215000 Jiangsu Peoples R China Univ Elect Sci & Technol China Chengdu Sichuan Peoples R China Macqaurie Univ Dept Comp Sydney NSW 2109 Australia Univ Queensland Sch Informat Technol & Elect Engn St Lucia Qld 4072 Australia

graph pattern matching (GPM) has been used in lots of areas, like biology, medical science, and physics. With the advent of Online Social Networks (OSNs), recently, GPM has been playing a significant role in social network analysis, which has been widely used in, for example, finding experts, social community mining, and social position detection. Given a query which contains a pattern graph G(Q) and a data graph G(D), a GPM algorithm finds those subgraphs, G(M), that match G(Q) in G(D). However, the existing GPM methods do not consider the multiple end-to-end constraints of the social contexts, like social relationships, social trust, and social positions on edges in G(Q), which are commonly found in various applications, such as crowdsourcing travel, social network based e-commerce, and study group selection, etc. In this paper, we first conceptually extend Bounded Simulation to Multi-Constrained Simulation (MCS), and propose a novel NP-Complete Multi-Constrained graph pattern matching (MC-GPM) problem. Then, to address the efficiency issue in large-scale MC-GPM, we propose a new concept called Strong Social Component (SSC), consisting of participants with strong social connections. We also propose an approach to identifying SSCs, and propose a novel index method and a graph compression method for SSC. Moreover, we devise a multithreading heuristic algorithm, called M-HAMC, to bidirectionally search the MC-GPM results in parallel without decompressing graphs. An extensive empirical study over five real-world large-scale social graphs has demonstrated the effectiveness and efficiency of our approach.

关键词： graph pattern matching social graph

来源：评论

学校读者我要写书评

暂无评论

Efficient parallel edge-centric approach for relaxed graph pattern matching

引用

JOURNAL OF SUPERCOMPUTING 2022年第2期78卷 1642-1671页

作者： Bouhenni, Sarra Yahiaoui, Said Nouali-Taboudjemat, Nadia Kheddouci, Hamamache Ecole Natl Super Informat BP M68 Oued Smar 16309 Algeria CERIST Ctr Rech Informat Sci & Tech Ben Aknoun 16030 Algeria Univ Lyon Univ Lyon 1 UMR5205 LIRISCNRS F-69622 Lyon France

Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.

关键词： graph pattern matching Subgraph matching graph simulation Dual simulation Massive graph Parallel algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：