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$
1
  • $\begingroup$ The question in the title does not match the question in the body of the post. I am not sure exactly what you are asking, but each post should ask only a single question. Rather than asking for the running time of two different data structures, it would be best to ask for the running time of only a single ata structure. $\endgroup$
    – D.W. ♦
    Commented Nov 30 at 22:11

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$
1

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