引用Genbox · 2022-10
“The paper includes comparisons with Ribbon filter”
指出这篇论文包含与 Ribbon filter 的对比
提出二元融合过滤器,存储逼近理论下限且构建更快
Xor 过滤器的存储量在理论下限的 23% 以内,而 Bloom 过滤器是 44%。受 Dietzfelbinger 与 Walzer 启发,论文构建了二元融合过滤器(binary fuse filter),存储在下限的 13% 以内且不牺牲查询速度,构建速度还可以比 xor 过滤器快一倍以上;稍微牺牲查询速度,可进一步把存储降到下限的 8% 以内。作者与 Bloom、分块 Bloom、向量商过滤器、cuckoo 和 ribbon 过滤器等方案比较,实验表明二元融合过滤器优于 xor 过滤器。
HN 评论者提到它多半是作为 xor 过滤器的改进版来引用,例如指出论文含有与 Ribbon 过滤器的比较,或说明自己在实现中配合基数排序使用。
候选里和二元融合过滤器直接相关的是 Xor 过滤器和 Ribbon 过滤器,读完能看清近似集合成员过滤器在空间与速度上的演进。
二元融合过滤器是对 Xor 过滤器的直接改进。
读Xor 过滤器的构造(三个哈希、剥离)与空间开销。
目标论文:存储更接近理论下限且构建更快的过滤器。
读融合图的构造、与 Xor 过滤器的差别,以及空间与速度对比。
“The paper includes comparisons with Ribbon filter”
“We have used radix sorting for the binary fuse filter Binary Fuse Filters.”