Folding and Unfolding Bloom filters- An Off-line Planning and On-Line Planning Optimization Problem

Abstract : The Internet of things has reached a stage that allows ubiquitous data access. Still, practical limitations remain in networks with scarce bandwidth. Here, we examine the Bloom filter data structure and its use in distributed protocols. We discuss how to minimize the bandwidth and energy usage consumed when distributed protocols exchange Bloom filters, through dynamic Bloom filter resizing. We propose a general and novel formalization of Bloom filter resizing, through foldings and unfoldings. The key challenge in the folding approach is determining suitable parameters and how to perform a folding. Specifically, we address the number of times that a Bloom filter should be folded and optionally unfolded, and how to determine an ideal reduction factor for this process. We formulate our approach as off-line planning of the integer factorization problem (where the integers correspond to the size of a Bloom filter), and propose further directions for optimizing the dynamic folding and unfolding of a Bloom filter.
Document type :
Journal articles
Liste complète des métadonnées

https://hal.inria.fr/hal-00870899
Contributor : Francoise Sailhan <>
Submitted on : Tuesday, October 8, 2013 - 12:25:41 PM
Last modification on : Thursday, February 7, 2019 - 2:21:01 PM

Identifiers

  • HAL Id : hal-00870899, version 1

Citation

Francoise Sailhan, Mark-Oliver Stehr. Folding and Unfolding Bloom filters- An Off-line Planning and On-Line Planning Optimization Problem. IEEE International Conference on Internet of Things, IEEE, 2012. ⟨hal-00870899⟩

Share

Metrics

Record views

106