Pattern Graph Change Oriented Incremental Graph Pattern Matching
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    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.

    Reference
    Related
    Cited by
Get Citation

张丽霞,王伟平,高建良,王建新.面向模式图变化的增量图模式匹配.软件学报,2015,26(11):2964-2980

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:February 28,2015
  • Revised:August 26,2015
  • Adopted:
  • Online: November 04,2015
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063