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.
Type de document :
Article dans une revue
IEEE International Conference on Internet of Things, IEEE, 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00870899
Contributeur : Francoise Sailhan <>
Soumis le : mardi 8 octobre 2013 - 12:25:41
Dernière modification le : mardi 8 octobre 2013 - 12:25:41

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

80