Incrementally Updatable Bloom Filter and Network Application

MyungKeun YOON

IEICE TRANSACTIONS on Communications   Vol.E92-B    No.11    pp.3484-3486
Publication Date: 2009/11/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E92.B.3484
Print ISSN: 0916-8516
Type of Manuscript: LETTER
Category: Fundamental Theories for Communications
Bloom filter,  network caching,  streaming algorithm,  

Full Text: PDF(109.7KB)>>
Buy this Article

Bloom filters are widely used for various network applications. Because of the limited size of on-chip memory and the large volume of network traffic, Bloom filters are often required to update their contents incrementally. Two techniques have been used for this purpose: cold cache and double buffering. Cold cache outperforms double buffering in terms of the average cache ratio. However, double buffering works much better than cold cache for the worst-case cache hit ratio. In this paper, we propose a new updating scheme for Bloom filters, which updates the contents of Bloom filter incrementally while the assigned memory space is fully utilized. The proposed scheme works better than cold cache in terms of the average cache hit ratio. At the same time, it outperforms double buffering for the worst-case cache hit ratio.