Triest: Counting local and global triangles in fully dynamic streams with fixed memory size
ACM Transactions on Knowledge Discovery from Data (TKDD), 2017•dl.acm.org
“Ogni lassada xe persa.” 1--Proverb from Trieste, Italy. We present trièst, a suite of one-pass
streaming algorithms to compute unbiased, low-variance, high-quality approximations of the
global and local (ie, 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 (eg …
streaming algorithms to compute unbiased, low-variance, high-quality approximations of the
global and local (ie, 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 (eg …
“Ogni lassada xe persa.”1-- Proverb from Trieste, Italy.
We present trièst, 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 trièst outperforms state-of-the-art approaches in accuracy and exhibits a small update time.
ACM Digital Library以上显示的是最相近的搜索结果。 查看全部搜索结果