Edinburgh Research Explorer

Adding Counting Quantifiers to Graph Patterns

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Title of host publicationACM SIGMOD Conference on Management of Data (SIGMOD 2016)
PublisherACM
Pages1215-1230
Number of pages16
ISBN (Print)978-1-4503-3531-7
DOIs
Publication statusPublished - 2016
Event2016 ACM SIGMOD Conference on Management of Data - San Francisco, United States
Duration: 26 Jun 20161 Jul 2016
http://sigmod2016.org/

Conference

Conference2016 ACM SIGMOD Conference on Management of Data
Abbreviated titleSIGMOD 2016
CountryUnited States
CitySan Francisco
Period26/06/161/07/16
Internet address

Abstract

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.

Event

2016 ACM SIGMOD Conference on Management of Data

26/06/161/07/16

San Francisco, United States

Event: Conference

Download statistics

No data available

ID: 24353712