论文标题
二进制保险丝过滤器：快速且小于XOR过滤器
Binary Fuse Filters: Fast and Smaller Than Xor Filters
论文作者
论文摘要
在使用很少的内存的同时，Bloom和Cuckoo过滤器提供了快速的近似设置会员资格。工程师使用它们来避免昂贵的磁盘和网络访问。最近引入的XOR过滤器可以比Bloom和Duckoo过滤器更快，更小。 XOR过滤器的存储空间为23％，而Bloom过滤器为44％。受Dietzfelbinger和Walzer的启发，我们构建了概率过滤器（称为二进制保险丝滤波器），它们不超过存储下限的13％，而无需牺牲查询速度。作为另一个好处，新的二进制保险丝过滤器的构建速度可能是XOR过滤器的构造速度的两倍以上。通过稍微牺牲查询速度，我们将存储量进一步降低到下限的8％以内。我们将性能与广泛的竞争替代方案进行比较，例如Bloom过滤器，Bloom Filters，Vector Filters Filters，Cuckoo Filters和最近的Ribbon Filters进行比较。我们的实验表明，二进制保险丝过滤器优于XOR过滤器。
Bloom and cuckoo filters provide fast approximate set membership while using little memory. Engineers use them to avoid expensive disk and network accesses. The recently introduced xor filters can be faster and smaller than Bloom and cuckoo filters. The xor filters are within 23% of the theoretical lower bound in storage as opposed to 44% for Bloom filters. Inspired by Dietzfelbinger and Walzer, we build probabilistic filters -- called binary fuse filters -- that are within 13% of the storage lower bound -- without sacrificing query speed. As an additional benefit, the construction of the new binary fuse filters can be more than twice as fast as the construction of xor filters. By slightly sacrificing query speed, we further reduce storage to within 8% of the lower bound. We compare the performance against a wide range of competitive alternatives such as Bloom filters, blocked Bloom filters, vector quotient filters, cuckoo filters, and the recent ribbon filters. Our experiments suggest that binary fuse filters are superior to xor filters.
