A Tight Lower Bound for High Frequency Moment Estimation with Small Error
作者： Yi Li , David P. Woodruff
DOI: 10.1007/978-3-642-40328-6_43
关键词:
摘要: We show an Ω((n 1 − 2/p logM)/e 2) bits of space lower bound for (1 + e)-approximating the p-th frequency moment \(F_p = \|x\|_p^p \sum_{i=1}^n |x_i|^p\) a vector x ∈ { M, M 1, …, M} n with constant probability in turnstile model data streams, any p > 2 and e ≥ 1/n 1/p (we require since there is trivial O(n logM) upper bound). This matches complexity Ganguly . again optimal < 1/log O(1) n.
springer.com
sci-hub.st 参考文章(46)
Christos H. Papadimitriou, Ziv Bar-Yossef, The complexity of massive data set computations University of California at Berkeley. ,(2002)
Sumit Ganguly, Lower Bounds on Frequency Estimation of Data Streams (Extended Abstract) Computer Science – Theory and Applications. pp. 204- 215 ,(2008) , 10.1007/978-3-540-79709-8_22
Guandong Xu, Yanchun Zhang, Lin Li, Algorithms and Techniques Springer US. pp. 29- 68 ,(2011) , 10.1007/978-1-4419-7735-9_3
Eyal Kushilevitz, Noam Nisan, Communication Complexity: Index of Notation ,(1996) , 10.1017/CBO9780511574948
Anirban DasGupta, Asymptotic Theory of Statistics and Probability ,(2008)
Moses Charikar, Kevin Chen, Martin Farach-Colton, Finding Frequent Items in Data Streams international colloquium on automata languages and programming. ,vol. 312, pp. 693- 703 ,(2002) , 10.1016/S0304-3975(03)00400-6
Vladimir Braverman, Rafail Ostrovsky, Recursive Sketching For Frequency Moments arXiv: Data Structures and Algorithms. ,(2010)
T. S. Jayram, Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. ,vol. 5687, pp. 562- 573 ,(2009) , 10.1007/978-3-642-03685-9_42
Sumit Ganguly, Polynomial Estimators for High Frequency Moments arXiv: Data Structures and Algorithms. ,(2011)
Alexandr Andoni, Huy L. Nguyễn, Yury Polyanskiy, Yihong Wu, Tight Lower Bound for Linear Sketches of Moments Automata, Languages, and Programming. pp. 25- 32 ,(2013) , 10.1007/978-3-642-39206-1_3