Pattern graph change oriented incremental graph pattern matching

被引：0

作者：

Zhang, Li-Xia ^{[1
,2
]}

Wang, Wei-Ping ^{[1
]}

Gao, Jian-Liang ^{[1
]}

Wang, Jian-Xin ^{[1
]}

机构：

[1] School of Information Science and Engineering, Central South University, Changsha

[2] School of Mathematics and Computer Science, Hu'nan Normal University, Changsha

来源：

Ruan Jian Xue Bao/Journal of Software | 2015年 / 26卷 / 11期

关键词：

Big data; Dynamic graph; Graph pattern matching; Incremental algorithm;

D O I：

10.13328/j.cnki.jos.004891

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In the age of big data, with the scales of data graphs growing rapidly, incremental graph pattern matching algorithm has become the research focus since it can avoid re-computing matches in the whole data graph and reduce the response time when the data graph or the pattern graph update. Considering the scenario where the data graph is constant while the pattern graph is changing in practical application, a pattern graph change oriented incremental graph pattern matching algorithm named PGC_IncGPM is proposed. The appropriate intermediate results generated in the process of graph pattern matching are recorded as indexes for subsequent pattern matching. An enhanced graph pattern matching algorithm named GPMS is presented for the first time for graph matching in the whole data graph. On one hand, the algorithm can build indexes for the subsequent incremental matching; on the other hand, it reduces the execution time of matching in the data graph. Two core subalgorithms designated to adding and reducing edges in the patter graph are designed and realized. No matter what mode changes in the pattern graph, incremental graph pattern matching can be carried out by combining these two subalgorithms. Experiments on real datasets and synthetic data show that PGC_IncGPM can effectively reduce the graph pattern matching execution time. Compared with the ReComputing algorithm which re-computes matches starting from scratch in the whole data graph, if the number of changed edges does not exceed the number of unchanged edges, the proposed algorithm can reduce execution time effectively. With the scale of the data graph increases, the reduction in execution time of PGC_IncGPM algorithm is more obvious, demonstrating the algorithm's applicability for large-scale data graph. © Copyright 2015, Institute of Software, the Chinese Academy of Sciences. All rights reserved.

引用

页码：2964 / 2980

页数：16

共 17 条

[1]

Schenker A., Last M., Bunke H., Kandel A., Classification of Web documents using a graph model, Proc. of the 7th Int'l Conf. on Document Analysis and Recognition (ICDAR 2003), pp. 240-244, (2003)

[2]

Liu C., Chen C., Han J.W., Philip S.Yu., GPLAG: Detection of software plagiarism by program dependence graph analysis, Proc. of the 12th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining (KDD 2006), pp. 872-881, (2006)

[3]

Fan W.F., Li J.Z., Luo J.Z., Tan Z.J., Wang X., Wu Y.H., Incremental graph pattern matching, Proc. of the 2011 ACM SIGMOD Int'l Conf. on Management of Data (SIGMOD 2011), pp. 925-936, (2011)

[4]

Stotz A., Nagi R., Sudit M., Incremental graph matching for situation awareness, Proc. of the 12th Int'l Conf. on Information Fusion (FUSION 2009), pp. 452-459, (2009)

[5]

Wang C., Chen L., Continuous subgraph pattern search over graph streams, Proc. of the 25th Int'l Conf. on Data Engineering (ICDE 2009), pp. 393-404, (2009)

[6]

Gao J., Zhou C., Zhou J.S., Yu J., Continuous pattern detection over billion-edge graph using distributed framework, Proc. of the 30th Int'l Conf. on Data Engineering (ICDE 2014), pp. 556-567, (2014)

[7]

Shang H., Zhang Y., Lin X., Yu J., Taming verification hardness: An efficient algorithm for testing subgraph isomorphism, Proc. of the VLDB Endowment, 1, 1, pp. 364-375, (2008)

[8]

Zhao P., Han J., On graph query optimization in large networks, Proc. of the VLDB Endowment, 3, 1, pp. 340-351, (2010)

[9]

Sun Z., Shao B., Wang H.Z., Li J.Z., Wang H.X., Efficient subgraph matching on billion node graphs, Proc. of the VLDB Endowment, 5, 9, pp. 788-799, (2012)

[10]

Fan W.F., Li J.Z., Ma S., Wang H.Z., Wu Y.H., Graph homomorphism revisited for graph matching, Proc. of the VLDB Endowment, 3, 1, pp. 1161-1172, (2010)

← 1 2 →