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

Simple Set Sketching

Jakob Bæk Tejs Houen, Rasmus Pagh, Stefan Walzer · 2022
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2022-12-13 · 最近 2025-07-19
2不同的人
2活跃月份
2讨论串
0被引(OpenAlex)
arXiv 摘要(候选层不写导读)

Imagine handling collisions in a hash table by storing, in each cell, the bit-wise exclusive-or of the set of keys hashing there. This appears to be a terrible idea: For $αn$ keys and $n$ buckets, where $α$ is constant, we expect that a constant fraction of the keys will be unrecoverable due to collisions. We show that if this collision resolution strategy is repeated three times independently the situation reverses: If $α$ is below a threshold of $\approx 0.81$ then we can recover the set of all inserted keys in linear time with high probability. Even though the description of our data structure is simple, its analysis is nontrivial. Our approach can be seen as a variant of the Invertible Bloom Filter (IBF) of Eppstein and Goodrich. While IBFs involve an explicit checksum per bucket to decide whether the bucket stores a single key, we exploit the idea of quotienting, namely that some bits of the key are implicit in the location where it is stored. We let those serve as an implicit checksum. These bits are not quite enough to ensure that no errors occur and the main technical challenge is to show that decoding can recover from these errors.

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

HN 书评

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

“One issue with this technique is when the set of characters grow above 64, so you can no longer give each one a unique bit. This could happen if we are instead interested in a window of unique words in a long document. Amazingly there is still a solution based on XOR! It is a variant of Bloom Filters, which I know everyone loves, but it uses XOR instea…”

A Neat XOR Trick原评论 ↗
评论hundredwatt · 2025-07

“> To be pedantic, not guaranteed. The xor of multiple elements may erroneously have a passing checksum, resulting in an undetected false decode The false decodes can be detected. During peeling, deleting a false decode inserts a new element with the opposite sign of count. Later, you decode this second false element and end up with the same element in bo…”

Extending That XOR Trick to Billions of Rows原评论 ↗