Counting Arbitrary Subgraphs in Data Streams

Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, He Sun

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

Abstract

We study the subgraph counting problem in data streams. We provide the first non-trivial estimator for approximately counting the number of occurrences of an arbitrary subgraph H of constant size in a (large) graph G. Our estimator works in the turnstile model, i.e., can handle both edge-insertions and edge-deletions, and is applicable in a distributed setting. Prior to this work, only for a few non-regular graphs estimators were known in case of edge-insertions, leaving the problem of counting general subgraphs in the turnstile model wide open. We further demonstrate the applicability of our estimator by analyzing its concentration for several graphs H and the case where G is a power law graph.
Original languageEnglish
Title of host publicationAutomata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II
PublisherSpringer Berlin Heidelberg
Pages598-609
Number of pages12
ISBN (Electronic)978-3-642-31585-5
ISBN (Print)978-3-642-31584-8
DOIs
Publication statusPublished - 2012
Event39th International Colloquium, ICALP 2012 - University of Warwick, Warwick, United Kingdom
Duration: 9 Jul 201213 Jul 2012
https://warwick.ac.uk/fac/cross_fac/dimap/icalp2012/

Conference

Conference39th International Colloquium, ICALP 2012
Abbreviated titleICALP 2012
Country/TerritoryUnited Kingdom
CityWarwick
Period9/07/1213/07/12
Internet address

Fingerprint

Dive into the research topics of 'Counting Arbitrary Subgraphs in Data Streams'. Together they form a unique fingerprint.

Cite this