HyperMinHash: MinHash in LogLog space

Abstract

In this extended abstract, we describe and analyze a lossy compression of MinHash from buckets of size $O\left(logn\right)$ to buckets of size $O\left(loglogn\right)$ 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 an additive approximation error $ϵ$ on a Jaccard index $t$, given a random oracle, HyperMinHash needs $O\left({ϵ}^{-2}(loglogn+log\frac{1}{ϵ}\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% using 2MiB of memory; MinHash can only estimate Jaccard indices for cardinalities of ${10}^{10}$ with the same memory consumption.

Keywords: compression; hyperloglog; min-wise hashing; sketching; streaming.