Binary fuse filters: Fast and smaller than xor filters (2022)
73 points
4 days ago
| 3 comments
| arxiv.org
| HN
dang
2 hours ago
[-]
Related prior work:

Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters - https://news.ycombinator.com/item?id=22742905 - March 2020 (25 comments)

Xor Filters: Faster and Smaller Than Bloom Filters - https://news.ycombinator.com/item?id=21840821 - Dec 2019 (81 comments)

reply
vgb2k18
1 hour ago
[-]
Fast, but not faster than XOR filters. I was wondering if the title was a typo, but the article clarifies they sacrificed some speed for the smaller size.
reply
nine_k
28 minutes ago
[-]
One construction is smaller and faster to build than xor filters, and another is even more compact, though slower:

> 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.

reply
djmips
2 hours ago
[-]
This feels like a better xor filter implementation.
reply