Tight Lower Bound for Linear Sketches of Moments
作者： Alexandr Andoni , Huy L. Nguyễn , Yury Polyanskiy , Yihong Wu
DOI: 10.1007/978-3-642-39206-1_3
关键词:
摘要: The problem of estimating frequency moments a data stream has attracted lot attention since the onset streaming algorithms [AMS99]. While space complexity for approximately computing pth moment, p∈(0,2] been settled [KNW10], p>2 exact remains open. For current best algorithm uses O(n1−2/plogn) words [AKO11,BO10], whereas lower bound is Ω(n1−2/p) [BJKS04]. In this paper, we show tight Ω(n1−2/plogn) class based on linear sketches, which store only sketch Ax input vector x and some (possibly randomized) matrix A. We note that all known are sketches.
arxiv.org
core.ac.uk
springer.com
princeton.edu
arxiv-vanity.com参考文章(31)
Lucien M Le Cam, Asymptotic methods in statistical theory Springer-Verlag New York, Inc.. ,(1986)
Christos H. Papadimitriou, Ziv Bar-Yossef, The complexity of massive data set computations University of California at Berkeley. ,(2002)
Irina A. Suslina, Yu. I. Ingster, Nonparametric Goodness-of-Fit Testing Under Gaussian Models ,(2002)
Vladimir Braverman, Rafail Ostrovsky, Recursive Sketching For Frequency Moments arXiv: Data Structures and Algorithms. ,(2010)
Alexandre B. Tsybakov, Introduction to Nonparametric Estimation ,(2008)
Sumit Ganguly, Polynomial Estimators for High Frequency Moments arXiv: Data Structures and Algorithms. ,(2011)
Lucien Le Cam, Asymptotic methods in statistical decision theory ,(1986)
Mark G. Low, Chi-square lower bounds Institute of Mathematical Statistics Collections. ,vol. 6, pp. 22- 31 ,(2010) , 10.1214/10-IMSCOLL602
Sumit Ganguly, Graham Cormode, On Estimating Frequency Moments of Data Streams international workshop and international workshop on approximation randomization and combinatorial optimization algorithms and techniques. pp. 479- 493 ,(2007) , 10.1007/978-3-540-74208-1_35
Vladimir Braverman, Rafail Ostrovsky, Approximating Large Frequency Moments with Pick-and-Drop Sampling Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. pp. 42- 57 ,(2013) , 10.1007/978-3-642-40328-6_4