I detta dokument föreslås kvantifierade grafmönster (QGP), en utvidgning av grafmönster genom att stödja enkla räknekvantifieringar på kanter. Vi visar att QGP naturligt uttrycker universell och existentiell kvantifiering, numeriska och kvotaggregat, samt negation. Ännu bättre, den ökade expressiviteten kommer inte med ett mycket högre pris. Vi visar att kvantifierad matchning, dvs. grafmönster som matchar QGP, fortfarande är NP-komplett i avsaknad av negation, och är DP-komplett för allmänna QGP. Vi visar hur kvantifierad matchning kan utföras genom att införliva kvantifier kontroll i konventionella subgraph isomorfism metoder. Vi utvecklar också parallella skalbara algoritmer för kvantifierad matchning. Som en tillämpning av QGP introducerar vi kvantifierade grafföreningsregler definierade med QGP, för att identifiera potentiella kunder inom marknadsföring av sociala medier. Med hjälp av verkliga och syntetiska grafer verifierar vi experimentellt QGP:s effektivitet och skalbarheten hos våra algoritmer.
Mer nyligen, i REF, Fan et al. införde kvantifierade grafmönster (QGP), en förlängning av de klassiska SPARQL-grafmönstren med hjälp av enkla kvantifieringsfaktorer på kanterna.
Adding Counting Quantifiers to Graph Patterns
{'venue': "SIGMOD '16", 'journal': None, 'mag_field_of_study': ['Computer Science']}