2
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\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, 2017 at 12:12
  • $\begingroup$ Community votes, please: too broad? $\endgroup$
    – Raphael ♦
    Apr 2, 2017 at 12:12
  • $\begingroup$ I edited the question $\endgroup$
    – Adi Ml
    Apr 2, 2017 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, 2017 at 15:59
  • 1
    $\begingroup$ I changed the question $\endgroup$
    – Adi Ml
    Apr 3, 2017 at 7:25

1 Answer 1

Reset to default
0
$\begingroup$

Quotient Filter

Time complexity

The quotient filter offers a constant time complexity of O(1) on average with most operations. However, in the worst case, all operations might take logarithmic time complexity O(log(n)), where n is the number of buckets in the filter.

Space complexity

The quotient filter does not store the data items but a part of the fingerprint yielding a constant space complexity of O(1).

Reference: systemdesign.one

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.