Counting Arbitrary Subgraphs in Data Streams

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

doi:10.1007/978-3-642-31585-5_53

Counting Arbitrary Subgraphs in Data Streams

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

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English
Title of host publication	Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II
Publisher	Springer
Pages	598-609
Number of pages	12
ISBN (Electronic)	978-3-642-31585-5
ISBN (Print)	978-3-642-31584-8
DOIs	https://doi.org/10.1007/978-3-642-31585-5_53
Publication status	Published - 2012
Event	39th International Colloquium, ICALP 2012 - University of Warwick, Warwick, United Kingdom Duration: 9 Jul 2012 → 13 Jul 2012 https://warwick.ac.uk/fac/cross_fac/dimap/icalp2012/

Conference

Conference	39th International Colloquium, ICALP 2012
Abbreviated title	ICALP 2012
Country/Territory	United Kingdom
City	Warwick
Period	9/07/12 → 13/07/12
Internet address	https://warwick.ac.uk/fac/cross_fac/dimap/icalp2012/

Access to Document

10.1007/978-3-642-31585-5_53

https://link.springer.com/chapter/10.1007%2F978-3-642-31585-5_53#aboutcontent

Cite this

@inproceedings{e3f5f8be646a4670b80d253cde8d3615,

title = "Counting Arbitrary Subgraphs in Data Streams",

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.",

author = "Kane, {Daniel M.} and Kurt Mehlhorn and Thomas Sauerwald and He Sun",

year = "2012",

doi = "10.1007/978-3-642-31585-5_53",

language = "English",

isbn = "978-3-642-31584-8",

pages = "598--609",

booktitle = "Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II",

publisher = "Springer",

address = "United Kingdom",

note = "39th International Colloquium, ICALP 2012, ICALP 2012 ; Conference date: 09-07-2012 Through 13-07-2012",

url = "https://warwick.ac.uk/fac/cross_fac/dimap/icalp2012/",

}

Kane, DM, Mehlhorn, K, Sauerwald, T & Sun, H 2012, Counting Arbitrary Subgraphs in Data Streams. in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II. Springer, pp. 598-609, 39th International Colloquium, ICALP 2012, Warwick, United Kingdom, 9/07/12. https://doi.org/10.1007/978-3-642-31585-5_53

TY - GEN

T1 - Counting Arbitrary Subgraphs in Data Streams

AU - Kane, Daniel M.

AU - Mehlhorn, Kurt

AU - Sauerwald, Thomas

AU - Sun, He

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-31585-5_53

DO - 10.1007/978-3-642-31585-5_53

M3 - Conference contribution

SN - 978-3-642-31584-8

SP - 598

EP - 609

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part II

PB - Springer

T2 - 39th International Colloquium, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -

Counting Arbitrary Subgraphs in Data Streams

Abstract

Conference

Access to Document

Fingerprint

Cite this