How does KMV (k minimum value) perform set intersection better than hyperloglog?

Question

In this paper, the author seems to suggest that theta sketches(a variant of kmv) outperforms hyperloglog in cardinality estimation on the intersection of n way streams.

Set Intersection. multiKMV can be tweaked in a natural way to handle set intersection and other set operations.

I am having a hard time understanding how intersection on kmv set can perform intersection accurately

The way I understand it, KMV can be describe by the following

Given a stream of number $x = [x_1, .... x_n]$ if we hash each number in $x$ and produce $h = [hash(x_1).....hash(x_n)]$

KMV attempts to represents and capture the characteristic of the stream by storing $k$ minimum value of $h$

The intersection of 2 streams is basically the naive intersection of 2 kmv set.

However this can't be true because if its true the operation is lossy, and probably cannot sustain more than a couple intersection without loosing its accuracy on estimating cardinality.

Can someone point me a direction on how kmv achieve accurate cardinality estimation of 2 or more streams?

Answer 1

There is no sketching algorithm that is able to estimate the intersection cardinalities without accuracy loss. What is meant by the paper is that it is easy to construct KMV sketches that represent the intersection. However, given two $k$-minimum value sketches, you usually cannot construct a $k$-minimum value sketch for the intersection. You rather end up with a $k'$-minimum value sketch with $k'$ smaller than $k$. Since the number of hashes kept within the KMV sketch determines the estimation accuracy, calculating the intersection also comes with accuracy loss.

For HyperLogLog sketches there is no natural way to construct a HyperLogLog that represents the intersection which makes it more difficult to estimate the intersection cardinality. Since HyperLogLogs can be easily merged, a popular way is to use the inclusion-exclusion principle $|A\cap B| = |A| + |B| - |A\cup B|$ to calculate the intersection cardinality. As investigated by the paper, the accuracy loss of this approach is usually much worse than calculating the intersection cardinality for KMV sketches. However, there also exists another (much more complex) technique for HyperLogLogs which uses the maximum-likelihood method and gives better estimates than the inclusion-exclusion principle, see https://arxiv.org/abs/1702.01284.