I'm currently using the Heavy-Hitters algorithm as described here and I'm wondering what if any space, time, accuracy, or real-world performance differences I would see if I were to switch to an implementation of Count-min Sketch plus a linked list to store the "heavy hitters" instead?

As far as I can tell, both require $O(k)$ space where $k$ is the number of heavy hitters to track; both $O(k)$ time to retreive the ordered values; to insert values the former requires $O(1)$ time, the latter $O(\ln{{1}\over{δ}})$. The accuracy and real-world performance differences I'm not sure about and have struggled to find write-ups that aren't too notation heavy that I can understand.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.