Tight Lower Bound for Linear Sketches of Moments
The problem of estimating frequency moments of a data stream has attracted a lot of attention since the onset of streaming algorithms [AMS99]. While the space complexity for approximately computing the p [superscript th] moment, for p ∈ (0,2] has been settled [KNW10], for p > 2 the exact complexi...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90562 https://orcid.org/0000-0002-2109-0979 |