In which we comment on several other options for implementing filters, derived from the ones we've already seen.
Other Options
The filters we've seen aren't the only ones, and many enhancements exist; in this section, we'll cover a few and note how they differ from the ones we've already discussed. Links to the original articles will be included, so you can learn more.
However, we aren't trying to cover every variant and development; that would require a far longer article and would probably be out of date as soon as it's published, so googling for more possibilities is up to you!
Let's go with just half a dozen important options.
Counting Quotient Filters extend QFs in two ways: they restructure metadata bits to obtain fast lookups at high load factors (even around 95%) and store counts in the table so repeated elements are included only once, saving space. Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro created this structure and described it in their paper, "A General-Purpose Counting Filter: Making Every Bit Count".
Vector Quotient Filters also target performance at high load factors, with small extra space cost. They are built from small blocks that behave like miniature QFs; another difference is that when an item may go into two free blocks, they pick the less full one to better balance the load. This structure was described in the "Vector Quotient Filters: Overcoming the Time/Space Trade-Off in Filter Design" article by Prashant Pandey, Alex Conway, Joe Durie, Michael A. Bender, Martin Farach-Colton, and Rob Johnson.
Morton Filters are a redesign of CFs, by Alex Breslow and Nuwan Jayasena, who described it in their "Morton Filters: Faster, Space-Efficient Cuckoo Filters via Biasing, Compression, and Decoupled Logical Sparsity" paper. The filter combines biasing (most items are placed with a single hash), compression (fullness counters track the load of each logical bucket), and overflow tracking (an array records overflowed blocks, so find knows whether to check a second location). The paper reports lookups up to 2.5✕ faster, insertions up to 15.5✕ faster, and deletions up to 1.6✕ faster than the cuckoo filter, while keeping space comparable. The gains are largest at high load, where cuckoo insertions slow down because of long eviction chains.
Vacuum Filters, by Minmei Wang, Mingxun Zhou, Shouqian Shi, and Chen Qian (see their "Vacuum Filters: More Space-Efficient and Faster
Replacement for Bloom and Cuckoo Filters" paper) do not need a table whose length is a power of 2 (avoiding unnecessary storage) by dividing it into chunks of L consecutive buckets (L being a power of 2) and keeping both candidates for an item in the same chunk, which improves cache locality. On average, they use 25% less space than CFs, which is their main advantage.Binary Fuse Filters are a direct successor to XFs, and in fact they were created by the same authors, Thomas Mueller Graf and Daniel Lemire, who described the structure in 2022 in their "Binary Fuse Filters: Fast and Smaller than XOR Filters" article. They keep the XF's query mechanism and nearly the same simple code. The idea is that the table is cut into many small segments laid in a row, and each value uses three consecutive segments instead of three positions each at one third of the array, and this structure requires only about 13% extra space instead of 23% for an XF.
Ribbon filters are also a descendant of the XF, and were created by Peter Dillinger and Stefan Walzer, who introduced the concept in their "Ribbon filter: practically smaller than Bloom and Xor" paper. Instead of having each value depend on several randomly distributed columns, each depends on a few consecutive columns with a varying starting column. This produces a system of equations that looks like a wavy diagonal band, which can be solved by an algorithm similar to Gaussian elimination. Space overhead is usually below 10% and can even go under 1% with some extra engineering.
Bye! In this series of articles, we've discussed Probabilistic Searching and studied several filters. This complements chapters 9 ("Searching") and 11 ("Bags, Sets, and Maps") in my book, with alternative requirements and implementations.
Want to get the book?
If you want the original, complete book, you can find it at the publisher, No Starch Press, or at Amazon, Barnes & Noble, Books-A-Million, Bookshop, Powell's Books, Target, or Walmart, in either paperback or e-book format.
Top comments (0)