Approximate Counting of Cycles in Streams

Madhusudan Manjunath; Kurt Mehlhorn; Konstantinos Panagiotou; He Sun

doi:10.1007/978-3-642-23719-5_57

Approximate Counting of Cycles in Streams

Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, He Sun

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naïve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions.

Original language	English
Title of host publication	Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings
Pages	677-688
Number of pages	12
ISBN (Electronic)	978-3-642-23719-5
DOIs	https://doi.org/10.1007/978-3-642-23719-5_57
Publication status	Published - 2011
Event	19th Annual European Symposium - Saarbrücken, Germany Duration: 5 Sept 2011 → 9 Sept 2011

Conference

Conference	19th Annual European Symposium
Abbreviated title	ESA 2011
Country/Territory	Germany
City	Saarbrücken
Period	5/09/11 → 9/09/11

Access to Document

10.1007/978-3-642-23719-5_57

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

Cite this

@inproceedings{aa9315d41c9e490bb62980761fc9b785,

title = "Approximate Counting of Cycles in Streams",

abstract = "We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the na{\"i}ve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions.",

author = "Madhusudan Manjunath and Kurt Mehlhorn and Konstantinos Panagiotou and He Sun",

year = "2011",

doi = "10.1007/978-3-642-23719-5_57",

language = "English",

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

pages = "677--688",

booktitle = "Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbr{\"u}cken, Germany, September 5-9, 2011. Proceedings",

note = "19th Annual European Symposium, ESA 2011 ; Conference date: 05-09-2011 Through 09-09-2011",

}

TY - GEN

T1 - Approximate Counting of Cycles in Streams

AU - Manjunath, Madhusudan

AU - Mehlhorn, Kurt

AU - Panagiotou, Konstantinos

AU - Sun, He

PY - 2011

Y1 - 2011

N2 - We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naïve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions.

AB - We consider the subgraph counting problem in data streams and develop the first non-trivial algorithm for approximately counting cycles of an arbitrary but fixed size. Previous non-trivial algorithms could only approximate the number of occurrences of subgraphs of size up to six. Our algorithm is based on the idea of computing instances of complex-valued random variables over the given stream and improves drastically upon the naïve sampling algorithm. In contrast to most existing approaches, our algorithm works in a distributed setting and for the turnstile model, i. e., the input stream is a sequence of edge insertions and deletions.

U2 - 10.1007/978-3-642-23719-5_57

DO - 10.1007/978-3-642-23719-5_57

M3 - Conference contribution

SN - 978-3-642-23718-8

SP - 677

EP - 688

BT - Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings

T2 - 19th Annual European Symposium

Y2 - 5 September 2011 through 9 September 2011

ER -

Approximate Counting of Cycles in Streams

Abstract / Description of output

Conference

Access to Document

Fingerprint

Cite this