Search papers, labs, and topics across Lattice.
This paper explores the utility of Counting Bloom Filters (CBFs) in providing certainty estimates for positive membership indications, addressing the limitations of traditional Bloom filters that only offer binary outputs. By leveraging the counter mechanism inherent in CBFs, the authors demonstrate that the certainty associated with membership can enhance the performance of machine learning models in applications such as caching and anomaly detection. The key result shows that incorporating certainty information significantly improves the accuracy and reliability of membership queries in network systems.
Certainty estimates from Counting Bloom Filters can transform how we approach membership queries in machine learning, enhancing both accuracy and reliability.
Hash-based data structures such as Bloom filters are widely used in network systems for tasks including caching, anomaly detection, and machine learning pipelines. They typically provide binary indications of whether an element belongs to a set of interest, e.g., the contents of a cache. When uncertainty arises due to hash collisions, a positive indication is returned to avoid false negatives. We argue that the certainty associated with such indications can itself be useful information. This work focuses on Counting Bloom Filters (CBFs), a Bloom-filter variant that maintains counters rather than bits. Besides supporting insertions and deletions, these counters provide additional information that can be used to estimate the certainty of positive membership indications. We show how this certainty signal can be exploited in architectures that combine Bloom Filters with machine learning (ML) models.
