An improved data stream algorithm for frequency moments
作者： Don Coppersmith , Ravi Kumar
关键词:
摘要: We present a simple, one-pass, O(√n)-space data stream algorithm for approximating the third frequency moment. This is first improvement to O(n2/3)-space of Alon, Matias, and Szegedy [AMS99]. current known lower bound this problem Ω(n1/3) [BJKS02a].Our can also be generalized an O(n1-1/(k-1))-space k-th Besides improving O(n1--1/k)-space upper [AMS99], our beats Ω(n1--1/k)-sampling [BKS01] problem.Our method suggests unified perspective space-efficient algorithms all moments.
acm.org
sci-hub.st 参考文章(17)
Sridhar Rajagopalan, Prabhakar Raghavan, Monika R. Henzinger, Computing on data streams External memory algorithms. pp. 107- 118 ,(1999)
Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, Luca Trevisan, Counting Distinct Elements in a Data Stream randomization and approximation techniques in computer science. pp. 1- 10 ,(2002) , 10.1007/3-540-45726-7_1
S. Muthukrishnan, Data Streams: Algorithms and Applications ,(2005)
Mark N. Wegman, J.Lawrence Carter, New hash functions and their use in authentication and set equality Journal of Computer and System Sciences. ,vol. 22, pp. 265- 279 ,(1981) , 10.1016/0022-0000(81)90033-7
Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar, Sampling algorithms Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 266- 275 ,(2001) , 10.1145/380752.380810
Brian Babcock, Shivnath Babu, Mayur Datar, Rajeev Motwani, Jennifer Widom, Models and issues in data stream systems symposium on principles of database systems. pp. 1- 16 ,(2002) , 10.1145/543613.543615
Ziv Bar-Yossef, D. Sivakumar, Ravi Kumar, Reductions in streaming algorithms, with an application to counting triangles in graphs symposium on discrete algorithms. pp. 623- 632 ,(2002) , 10.5555/545381.545464
Philippe Flajolet, G. Nigel Martin, Probabilistic counting algorithms for data base applications Journal of Computer and System Sciences. ,vol. 31, pp. 182- 209 ,(1985) , 10.1016/0022-0000(85)90041-8
Piotr Indyk, Stable distributions, pseudorandom generators, embeddings, and data stream computation Journal of the ACM. ,vol. 53, pp. 307- 323 ,(2006) , 10.1145/1147954.1147955
J.Lawrence Carter, Mark N. Wegman, Universal classes of hash functions Journal of Computer and System Sciences. ,vol. 18, pp. 143- 154 ,(1979) , 10.1016/0022-0000(79)90044-8