Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling
We study the problem of estimating the value of sums of the form S[subscript p]≜∑([x[subscript i] over p]) when one has the ability to sample x[subscript i]≥0 with probability proportional to its magnitude. When p=2 , this problem is equivalent to estimating the selectivity of a self-join query...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2018
|
| Online Access: | http://hdl.handle.net/1721.1/115241 https://orcid.org/0000-0001-5064-3221 https://orcid.org/0000-0002-4056-0489 https://orcid.org/0000-0002-6514-3761 https://orcid.org/0000-0002-3466-6543 https://orcid.org/0000-0002-4353-7639 |