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 |
| _version_ | 1826205390155546624 |
|---|---|
| author | Andoni, Alexandr Nguyen, Huy L. Polyanskiy, Yury Wu, Yihong |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Andoni, Alexandr Nguyen, Huy L. Polyanskiy, Yury Wu, Yihong |
| author_sort | Andoni, Alexandr |
| collection | MIT |
| description | 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 complexity remains open. For p > 2 the current best algorithm uses O(n [superscript 1 − 2/p] logn) words of space [AKO11,BO10], whereas the lower bound is of Ω(n [superscript 1 − 2/p]) [BJKS04].
In this paper, we show a tight lower bound of Ω(n [superscript 1 − 2/p] logn) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches. |
| first_indexed | 2024-09-23T13:12:15Z |
| format | Article |
| id | mit-1721.1/90562 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:12:15Z |
| publishDate | 2014 |
| record_format | dspace |
| spelling | mit-1721.1/905622022-10-01T13:43:09Z Tight Lower Bound for Linear Sketches of Moments Andoni, Alexandr Nguyen, Huy L. Polyanskiy, Yury Wu, Yihong Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Polyanskiy, Yury 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 complexity remains open. For p > 2 the current best algorithm uses O(n [superscript 1 − 2/p] logn) words of space [AKO11,BO10], whereas the lower bound is of Ω(n [superscript 1 − 2/p]) [BJKS04]. In this paper, we show a tight lower bound of Ω(n [superscript 1 − 2/p] logn) words for the class of algorithms based on linear sketches, which store only a sketch Ax of input vector x and some (possibly randomized) matrix A. We note that all known algorithms for this problem are linear sketches. National Science Foundation (U.S.). Center for Science of Information (Grant Agreement CCF-0939370) 2014-10-06T18:41:47Z 2014-10-06T18:41:47Z 2013 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-39205-4 978-3-642-39206-1 0302-9743 1611-3349 http://hdl.handle.net/1721.1/90562 Andoni, Alexandr, Huy L. Nguyen, Yury Polyanskiy, and Yihong Wu. “Tight Lower Bound for Linear Sketches of Moments.” Lecture Notes in Computer Science (2013): 25–32. https://orcid.org/0000-0002-2109-0979 en_US http://dx.doi.org/10.1007/978-3-642-39206-1_3 Automata, Languages, and Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf MIT web domain |
| spellingShingle | Andoni, Alexandr Nguyen, Huy L. Polyanskiy, Yury Wu, Yihong Tight Lower Bound for Linear Sketches of Moments |
| title | Tight Lower Bound for Linear Sketches of Moments |
| title_full | Tight Lower Bound for Linear Sketches of Moments |
| title_fullStr | Tight Lower Bound for Linear Sketches of Moments |
| title_full_unstemmed | Tight Lower Bound for Linear Sketches of Moments |
| title_short | Tight Lower Bound for Linear Sketches of Moments |
| title_sort | tight lower bound for linear sketches of moments |
| url | http://hdl.handle.net/1721.1/90562 https://orcid.org/0000-0002-2109-0979 |
| work_keys_str_mv | AT andonialexandr tightlowerboundforlinearsketchesofmoments AT nguyenhuyl tightlowerboundforlinearsketchesofmoments AT polyanskiyyury tightlowerboundforlinearsketchesofmoments AT wuyihong tightlowerboundforlinearsketchesofmoments |