Extending Graph Patterns with Conditions

CategoryPublications 288

Authors: Grace Fan, Wenfei Fan, Yuanhao Li, Ping Lu, Chao Tian, Jingren Zhou

Published in: ACM Conference on Management of Data(SIGMOD 2020), June 14-19, 2020, Portland Oregon, USA

Date of Publication: June 14, 2020


We propose an extension of graph patterns, referred to as conditional graph patterns and denoted as CGPs. In a CGP,one can specify a simple condition on each edge such that the edge exists if and only if the condition is satisfied. We show that CGPs allow us to catch missing links, increase the expressivity of graph functional dependencies, and provide a succinct representation of graph patterns. We settle the complexity of their consistency, matching, incremental matching and containment problems, in linear time,NP-complete,NP-complete and p2-complete, respectively. These tell us that despite the increased expressive power of CGPs, the matching and incremental matching problems for CGPs are no harder than their counterparts for conventional patterns. We develop algorithms for matching and incremental matching of CGPs, and for (incremental) multi-CGP matching and optimization. Using real-life and synthetic graphs, we empirically verify the efficiency and effectiveness of our algorithms.

View Full Text

Keywords2020Data qualitySIGMODSocial media marketingWenfei Fan Previous: Next: