2009/06/10 by MyungKeun Yoon · 1 citation
Computer Science · Materials Science · #Caching and Content Delivery #Covalent Organic Framework Applications #Carbon and Quantum Dots Applications #Bloom filter #Computer science #Network packet #Filter (signal processing) #Set (abstract data type) #Static random-access memory #Scheme (mathematics) #Memory management #Data structure #Computer network #Computer hardware #Semiconductor memory
paper · doi:10.1109/tkde.2009.136
openalex publication_date 2009/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
A Bloom filter is a simple but powerful data structure that can check membership to a static set. As Bloom filters become more popular for network applications, a membership query for a dynamic set is also required. Some network applications require high-speed processing of packets. For this purpose, Bloom filters should reside in a fast and small memory, SRAM. In this case, due to the limited memory size, stale data in the Bloom filter should be deleted to make space for new data. Namely the Bloom filter needs aging like LRU caching. In this paper, we propose a new aging scheme for Bloom filters. The proposed scheme utilizes the memory space more efficiently than double buffering, the current state of the art. We prove theoretically that the proposed scheme outperforms double buffering. We also perform experiments on real Internet traces to verify the effectiveness of the proposed scheme.