Binary fuse filters: Fast and smaller than xor filters (2022)
Summary
Binary Fuse Filters introduces a new probabilistic data structure that is claimed to be faster and smaller than XOR filters and closer to the theoretical lower storage bound. The paper shows that binary fuse filters can achieve higher storage efficiency with comparable query speed, and can be built faster than XOR filters, with a trade-off option to push storage efficiency even further at a small cost to speed. The work positions these filters against Bloom, vector quotient, and other contemporary filters, demonstrating favorable performance in several scenarios.