2013/06/26 by Alexandr Andoni, Huy L. Nguyen, Andoni, Alexandr +6
Computer Science · Mathematics · #Artificial Intelligence in Games #Computational Geometry and Mesh Generation #Data Management and Algorithms #cs.DS #cs.IT #math.IT #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1306.6295
In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), Riga, Latvia, July 2013
arxiv created 2013/06/26 · arxiv updated 2013/06/27
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\rm 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(n1-2/plog n) words of space [AKO11,BO10], whereas the lower bound is of Ω(n1-2/p) [BJKS04]. In this paper, we show a tight lower bound of Ω(n1-2/plog n) 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.