Shifting Filter: Reimagining Cuckoo Filters for Dynamic Multi-Functional Set Queries

TL;DR

Set queries—determining membership, set association, and element frequency—are the bedrock of modern networking and database systems. While Bloom Filters and Cuckoo Filters are staples, they struggle with "auxiliary" data like multiplicity and often fail to support deletions. Shifting Filter (SF) introduced in this paper provides a deletable, space-efficient framework that encodes metadata directly into the positional offset of a hash table, outperforming existing sketches by orders of magnitude in throughput and accuracy.

Problem & Motivation: The Static Filter Bottleneck

In high-performance systems (like CDNs or DDoS detectors), we don't just ask "Is this item here?" We often need to know "Which set does it belong to?" or "How many times have we seen it?"

Current solutions face a trilemma:

1. Functionality vs. Deletion: Bloom Filters are fast but hard to delete from. Counting Bloom Filters support deletion but blow up in space.
2. Parametric Limitations: Methods like Shifting Bloom Filter (ShBF) require knowing the maximum possible frequency (multiplicity) in advance. If the data is skewed, performance collapses.
3. Specialization: Most sketches are "one-trick ponies," optimized only for one type of query (e.g., membership only).

The authors' intuition was to leverage the Cuckoo Filter's ability to store fingerprints (allowing deletion) and extend it with a shifting mechanism to hide auxiliary info in plain sight—via the slot index.

Methodology: The Core Shifting Framework

The genius of the Shifting Filter lies in its use of offsets. Instead of just storing a fingerprint in a bucket determined by a hash $h(e)$, the framework partitions the table into blocks. An element's metadata (e.g., its count) is represented by the distance (offset) from its "base" block to its "actual" storage block.

Architectural Specifications

The paper proposes two main variants:

• SFS (Shifting Filter on Slots): Applies the shift vertically. It uses the slot index within candidate buckets to represent info.
• SFB (Shifting Filter on Buckets): Applies the shift horizontally across different buckets, prioritizing space-friendliness.

To handle extremely high multiplicities (e.g., a flow appearing 1 million times), they don't just shift 1 million slots. They introduce a small count field in each slot. The total value is calculated as: $extMultiplicity=extOffset+(extCountFieldValueimesextBlockSize)$ This "hybrid" encoding prevents the search range from becoming prohibitively large.

Experiments & Results: Crushing the Baselines

The evaluation used both synthetic data and real-world MAWI traffic traces.

1. Space and Efficiency

SF achieves a 98% load factor. Compared to standard Bloom Filters and the prior ShBF, it saves between 18% to 21% of memory for the same False Positive Rate (FPR).

2. Query Performance

In association queries (finding affiliations), the SFSA variant maintained stable throughput regardless of the number of sets. In contrast, ShBF's performance plummeted because its hash-count grew linearly with the number of sets.

Fig: Note how SFSM (our work) maintains competitive insertion speeds while existing filters like BF and ShBF are significantly slower in complex scenarios.

3. Real-world Robustness

On traffic traces with skewed distributions (heavy hitters), SFSX provided a hybrid query throughput 2623x faster than ShBF. This is because ShBF must scan a massive bit-range to estimate frequency, whereas SF jumps directly to candidate buckets.

Critical Analysis & Conclusion

Takeaways

• Positional Encoding: This paper demonstrates that where you store data is just as informative as what you store.
• Unified Design: By modularizing the "mark" and "count" fields, SF becomes a Swiss Army knife for system architects.

Limitations

The authors honestly note that while query and deletion are efficient, the absolute throughput (Mops/s) could be higher. The "kick-out" mechanism of Cuckoo hashing, while providing high density, introduces latency spikes during insertions in "crowded" filters.

Future Outlook

The move toward "non-parametric" sketches is vital. Future iterations might replace the manual "offset" logic with learned indexing to further optimize the trade-off between search range and memory density.