按年被提到
20172018 · 2 次2026
算法与数据结构›哈希、压缩与向量化·arXiv:1710.08436 · cs.DS

HyperMinHash: MinHash in LogLog space

Yun William Yu, Griffin M. Weber · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2018-01-09 · 最近 2018-11-14
2不同的人
2活跃月份
2讨论串
24被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论yunwilliamyu · 2018-01

“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 start pointing people to your Github repo too. [0]: https://arxiv.org/abs/171…”

Show HN: HyperLogLog intersections原评论 ↗
评论seiflotfy · 2018-11

“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 several of those HLLs... an even more naive just use the Jaccard Index with the HLL …”

HyperMinHash: Bringing intersections to HyperLogLog原评论 ↗