推荐thomasmg · 2025-05
“I know, there are other ways you could do error correction, but this is very fast, and quite interesting technically.”
推荐用 IBLT 发送小差量来做纠错,速度很快且技术上有趣
支持完整列出内容的布隆过滤器变体 IBLT
论文提出布隆过滤器的一个变体:除了键值对的插入、删除和查找,只要键值对数量低于设计阈值,还能以高概率完整列出全部内容。正常运行时数量可大幅超过阈值,只是暂时无法列出内容、查找成功率下降;删除条目使数量回落后一切恢复正常。简单变体还对删除未插入的键、给同一键插入两个不同值等常见错误保持稳健,适用于数据库和网络等应用。
HN 评论者提它是因为发送小体积的 IBLT 差异即可快速做纠错/集合对账,技术上很有趣。
“I know, there are other ways you could do error correction, but this is very fast, and quite interesting technically.”
“My information theory/coding theory is not strong enough to really know, but it might be worth looking into!”