按年被提到
20112014 · 1 次2026
系统、数据库与网络›分布式数据与 CRDT·arXiv:1101.2245 · cs.DS

Invertible Bloom Lookup Tables

可逆布隆查找表
Michael T. Goodrich, Michael Mitzenmacher · 2011

支持完整列出内容的布隆过滤器变体 IBLT

开始阅读 ↗PDFalphaXiv 讨论
被推荐 · 3 人首次 2014-08-29 · 最近 2025-05-02发表于 Allerton Conference on Communication, Control, and Computing
3不同的人
3活跃月份
3讨论串
197被引(OpenAlex)

论文提出布隆过滤器的一个变体:除了键值对的插入、删除和查找,只要键值对数量低于设计阈值,还能以高概率完整列出全部内容。正常运行时数量可大幅超过阈值,只是暂时无法列出内容、查找成功率下降;删除条目使数量回落后一切恢复正常。简单变体还对删除未插入的键、给同一键插入两个不同值等常见错误保持稳健,适用于数据库和网络等应用。

HN 为什么提它

HN 评论者提它是因为发送小体积的 IBLT 差异即可快速做纠错/集合对账,技术上很有趣。

方法难度 3 / 5约 40 分钟经得起时间
读之前最好知道
1布隆过滤器(Bloom filter)
2哈希表与哈希函数
3概率分析基础
4集合对账与纠错编码

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
推荐thomasmg · 2025-05

“I know, there are other ways you could do error correction, but this is very fast, and quite interesting technically.”

推荐用 IBLT 发送小差量来做纠错,速度很快且技术上有趣
Bloom Filters原评论 ↗
引用sgentle · 2016-03

“My information theory/coding theory is not strong enough to really know, but it might be worth looking into!”

提到 Invertible Bloom lookup tables,自己信息论功底不够,认为值得研究
The Difficulty of Private Contact Discovery原评论 ↗
被提交为 story · 1 次