what is the space and time complexity (lookup, insertion) of count-min sketch and quotient filter?

I could not find these complexities. I would like to make a program which find the frequencies of objects in a set in the fastest way, so the time complexity is really important for me.

I read the research article about those objects, about quotient filter from "Don’t Thrash: How to Cache your Hash on Flash", it was said there that its lookup and insert actions are faster than bloom filter which is O(k) (k is number of hash function).

I also read from "Count-Min Sketch" and "An Improved Data Stream Summary: The Count-Min Sketch and its Applications" but could not find the big O complexity of both of these data structures.

Thank you

  • $\begingroup$ A reference request like yours is too broad for Stack Exchange -- you ask for a survey of a whole research area! You need to narrow your focus considerably before a question of reasonable scope appears. Try talking to your advisor(s), search with Google Scholar and check out this guide to better (re)searches on Academia. $\endgroup$ – Raphael Apr 2 '17 at 12:12
  • $\begingroup$ Community votes, please: too broad? $\endgroup$ – Raphael Apr 2 '17 at 12:12
  • $\begingroup$ I edited the question $\endgroup$ – Adi Ml Apr 2 '17 at 12:44
  • 2
    $\begingroup$ Where did you look? What research have you done? Have you found a paper, lecture notes, or textbook that describes the count-min sketch? Do they discuss the space and time complexity? I would expect this to be covered in standard presentations of these data structures. $\endgroup$ – D.W. Apr 2 '17 at 15:59
  • 1
    $\begingroup$ I changed the question $\endgroup$ – Adi Ml Apr 3 '17 at 7:25

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.