Simulation-based Approximate Graph Pattern Matching

被引：2

作者：

Chen, Xiaoshuang ^{[1
]}

机构：

[1] Univ New South Wales, Sydney, NSW, Australia

来源：

SIGMOD'20: PROCEEDINGS OF THE 2020 ACM SIGMOD INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA | 2020年

关键词：

simulation; graph pattern matching; inexact matching; ALGORITHM;

D O I：

10.1145/3318464.3384401

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Graph pattern matching is a fundamental problem in analyzing attributed graphs, that is to search the matches of a given query graph in a large data graph. However, existing algorithms either encounter with the performance issues or cannot capture reasonable matches. In this paper, we propose a simulation-based approximate pattern matching algorithm that is not only efficient to compute, but also able to capture those reasonable matches (missed by existing algorithms).

引用

页码：2825 / 2827

页数：3

共 17 条

[1]

[Anonymous], 2011, P 2011 ACM SIGMOD IN

[2]

[Anonymous], 1979, Computers and intractability

[3]

[Anonymous], 1989, COMMUNICATION CONCUR

[4] Efficient Subgraph Matching by Postponing Cartesian Products [J].

Bi, Fei ;

Chang, Lijun ;

Lin, Xuemin ;

Qin, Lu ;

Zhang, Wenjie .

SIGMOD'16: PROCEEDINGS OF THE 2016 INTERNATIONAL CONFERENCE ON MANAGEMENT OF DATA, 2016, :1199-1214

[5] Neighbor-Aware Search for Approximate Labeled Graph Matching using the Chi-Square Statistics [J].

Dutta, Sourav ;

Nayek, Pratik ;

Bhattacharya, Arnab .

PROCEEDINGS OF THE 26TH INTERNATIONAL CONFERENCE ON WORLD WIDE WEB (WWW'17), 2017, :1281-1290

[6] Graph Pattern Matching: From Intractable to Polynomial Time [J].

Fan, Wenfei ;

Li, Jianzhong ;

Ma, Shuai ;

Tang, Nan ;

Wu, Yinghui ;

Wu, Yunpeng .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2010, 3 (01) :264-275

[7]

Fan WF, 2011, PROC INT CONF DATA, P39, DOI 10.1109/ICDE.2011.5767858

[8]

Han W.-S., 2013, P 2013 ACM SIGMOD IN, P337, DOI DOI 10.1145/2463676.2465300

[9] NeMa: Fast Graph Search with Label Similarity [J].

Khan, Arijit ;

Wu, Yinghui ;

Aggarwal, Charu C. ;

Yan, Xifeng .

PROCEEDINGS OF THE VLDB ENDOWMENT, 2013, 6 (03) :181-192

[10] Strong Simulation: Capturing Topology in Graph Pattern Matching [J].

Ma, Shuai ;

Cao, Yang ;

Fan, Wenfei ;

Huai, Jinpeng ;

Wo, Tianyu .

ACM TRANSACTIONS ON DATABASE SYSTEMS, 2014, 39 (01)

← 1 2 →