Journal
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
Volume 11, Issue 4, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/3059194
Keywords
Cycle counting; reservoir sampling; subgraph counting
Funding
- National Science Foundation [IIS-1247581]
- National Institutes of Health [R01-CA180776]
- Two Sigma Investments, LP
Ask authors/readers for more resources
We present TRIEST, a suite of one-pass streaming algorithms to compute unbiased, low-variance, high-quality approximations of the global and local (i.e., incident to each vertex) number of triangles in a fully dynamic graph represented as an adversarial stream of edge insertions and deletions. Our algorithms use reservoir sampling and its variants to exploit the user-specified memory space at all times. This is in contrast with previous approaches, which require hard-to-choose parameters (e.g., a fixed sampling probability) and offer no guarantees on the amount of memory they use. We analyze the variance of the estimations and show novel concentration bounds for these quantities. Our experimental results on very large graphs demonstrate that TRIEST outperforms state-of-the-art approaches in accuracy and exhibits a small update time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available