This question considers KMV, an algorithm that is able to estimate the cardinality (unique item) from a stream of data.

The way it does it is to first map the stream of data to a space that almost guarantee uniform distribution and then only store the minimum k values. To estimate the cardinality it looks at the spacing between the k values and extrapolate the cardinality.

One of the benefit of KMV compare to hyperloglog is that KMV can perform set intersection that create better result than hyperloglog with inclusion exclusion principle

I am looking at a particular implementation of KMV call theta sketch and I am interest in its implementation in intersection

Specifically I am having a hard time understanding how its k size is reducing almost 50% slower than my implementation.

I expect k's reduction to match the probably of intersection between the 2 sets, which I do see in my code. However I am seeing k's reduction in theta sketch much less prominent.

I look at the code and I think the only major difference is that theta sketch is much more optimized and its bound mechanism is through storing any number less than a certain number (ie. theta) instead of storing the minimum k number. But I still expect that k to reduce as fast as my implementation.

Can someone point me a direction ?

  • $\begingroup$ I doubt this is answerable without reviewing the code of those two implementations, and that task sounds outside of our scope here. Any community votes? $\endgroup$ – D.W. Apr 20 '19 at 22:40

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.