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
Specifically I am having a hard time understanding how its
k size is reducing almost 50% slower than my implementation.
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 ?