Projects per year
Abstract / Description of output
This paper proposes quantified graph patterns (QGPs), an extension of graph patterns by supporting simple counting quantifiers on edges. We show that QGPs naturally express universal and existential quantification, numeric and ratio aggregates, as well as negation. Better still, the increased expressivity does not come with a much higher price. We show that quantified matching, i.e., graph pattern matching with QGPs, remains NP-complete in the absence of negation,and is DP-complete for general QGPs. We show how quantified matching can be conducted by incorporating quantifier checking into conventional subgraph isomorphism methods.We also develop parallel scalable algorithms for quantified matching. As an application of QGPs, we introduce quantified graph association rules defined with QGPs, to identify potential customers in social media marketing. Using real-life and synthetic graphs, we experimentally verify the effectiveness of QGPs and the scalability of our algorithms.
|Title of host publication
|ACM SIGMOD Conference on Management of Data (SIGMOD 2016)
|Number of pages
|Published - 2016
|2016 ACM SIGMOD Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 2016 → 1 Jul 2016
|2016 ACM SIGMOD Conference on Management of Data
|26/06/16 → 1/07/16
FingerprintDive into the research topics of 'Adding Counting Quantifiers to Graph Patterns'. Together they form a unique fingerprint.
- 1 Finished
1/11/13 → 31/10/16