Name
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ï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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-23719-5_57 | ESA |
Keywords | Field | DocType |
input stream,complex-valued random variable,previous non-trivial algorithm,existing approach,non-trivial algorithm,algorithm work,edge insertion,sampling algorithm,approximate counting,data stream,fixed size | Discrete mathematics,Combinatorics,Data stream mining,Random variable,Turnstile,Computer science,Counting problem,Theoretical computer science,Sampling (statistics),STREAMS | Conference |
Volume | ISSN | Citations |
6942 | 0302-9743 | 20 |
PageRank | References | Authors |
0.76 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Madhusudan Manjunath | 1 | 31 | 3.58 |
| Kurt Mehlhorn | 2 | 5314 | 853.36 |
| Konstantinos Panagiotou | 3 | 290 | 27.80 |
| He Sun | 4 | 20 | 0.76 |