This question is about the second frequency algorithm described in N. Alon, T. Matias, and M. Szegedy The space complexity of approximating the frequency moments. Specifically, I am asking about the stochastic algorithm for the second moment.
It seems its usage it very much limited. The storage required is proportional to $O(log(1/e)/\lambda^2)$, where $\lambda$ is the relative error and $\epsilon$ is the success probability. Consider however a naive algorithm where a hash function of the given stream in the range $O(log(1/e)/\lambda^2)$ is computed and the respective array elements are updated. If there are no hash collisions this approach would be exact. But this means that for streams with $O(log(1/e)/\lambda^2)$ distinct elements the naive algorithm is unbeatable. If we require relative error to be $10^{-3}$ this means that by using 8MB one can already compute frequencies of huge streams containing millions of distinct elements. So, what's the point of using AMS?
