The space complexity of approximating the frequency moments
The space complexity of approximating the frequency moments
复制标题
DOI：
10.1006/jcss.1997.1545
复制
发表时间：
1999-02-01
影响因子：
1.1
通讯作者：
Szegedy, M
中科院分区：
文献类型：
--
作者：
Alon, N;Matias, Y;Szegedy, M
包含mi个类型i的元素的序列的频率矩，1小于或等于i小于或等于n，是数字F-k = Sigma（i=1）（n），m（i）（k）。我们考虑随机算法的空间复杂性，近似的数字F-k，当序列的元素是一个接一个地给出，不能存储。令人惊讶的是，数字F-0，F-1和F-2可以在对数空间中近似，而当k大于或等于6时，F-k的近似需要n（Omega（1））空间。也提到了数据库的应用。(C)北京：科学出版社.
The frequency moments of a sequence containing mi elements of type i, 1 less than or equal to i less than or equal to n, are the numbers F-k = Sigma(i=1)(n), m(i)(k). We consider the space complexity of randomized algorithms that approximate the numbers F-k, when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F-0, F-1, and F-2 can be approximated in logarithmic space, whereas the approximation of F-k for k greater than or equal to 6 requires n(Omega(1)) space. Applications to data bases are mentioned as well. (C) 1999 Academic Press.