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?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.