HyperMinHash: MinHash in LogLog space
Yun William Yu, Griffin M. Weber · IEEE Transactions on Knowledge and Data Engineering · 2020
In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size$O(\log n)$to buckets of size$O(\log \log n)$by encoding using floating-point notation. This new compressed sketch, which we call HyperMinHash, as we build off a HyperLogLog scaffold, can be used as a drop-in replacement of MinHash. Unlike comparable Jaccard index fingerprinting algorithms in sub-logarithmic space (such as b-bit MinHash), HyperMinHash retains MinHash's features of streaming updates, unions, and cardinality estimation. For a additive approximation error$\epsilon$on a Jaccard index$ t$, given a random oracle, HyperMinHash needs$O\left(\epsilon ^{-2} \left(\log \log n + \log \frac{1}{ \epsilon } \right)\right)$space. HyperMinHash allows estimating Jaccard indices of 0.01 for set cardinalities on the order of$10^{19}$with relative error of around 10 percent using 2MiB of memory; MinHash can only estimate Jaccard indices for cardinalities of$10^{10}$with the same memory consumption.