HackerPapers

arXiv:1710.08436cs.DS

HyperMinHash: MinHash in LogLog space

Yun William Yu, Griffin M. Weber

Abstract

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 multiplicative approximation error $1+ ε$ on a Jaccard index $ t $, given a random oracle, HyperMinHash needs $O\left(ε^{-2} \left( \log\log n + \log \frac{1}{ t ε} \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\% using 64KiB of memory; MinHash can only estimate Jaccard indices for cardinalities of $10^{10}$ with the same memory consumption.

arXiv comments
12 pages, 6 figures
Journal reference
DOI
Subjects
cs.DSData Structures and Algorithms cs.DBDatabases

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Jan 2018 to Nov 2018.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. HyperMinHash: Bringing intersections to HyperLogLog 1 comment

    • Author of the Library here: I can't fully agree that HyperLogLogs are good for intersections, that does not mean it can't be done, just there is always a high error rate. The easy way to do that is to maintain a separate MinHash sketch per HLL and use the Jaccard Index of…

      seiflotfyView on HNParent context

  2. Show HN: HyperLogLog intersections 1 comment

    • Thanks so much for producing a Golang implementation of our HyperMinHash paper (I'm the first author) [0] and pointing me to your Hackernews post! As an aside, we also have a prototype Python implementation [1], but your implementation looks more efficient than ours, and I may…

      yunwilliamyuView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.