[SS12] Folding and Unfolding Bloom Filters - an Off-line Planing and on Line-Optimisation

Rapport Scientifique : Date de dépot: 2012/08/27, Nb pages 8, (Tech. Rep.: CEDRIC-12-2629)

Mots clés: Bloom filter, Folding Un-Folding, Internet of the things

Résumé: The Internet of the things has reached a stage that enables an easy access to information and services anywhere, anytime. However, such vision still comes with practical limitation mainly relating to limited bandwidth and energy. It is henceforth crucial to devise novel solutions for supporting lightweight networking, data flow and service access so as to impact as less as possible bandwidth and energy. This paper touches upon such an issue by resizing the Bloom filter, which hence permits to keep to a minimum the bandwith and energy usage associated with exchanging a Bloom filter. The basic idea consists in folding or unfolding a Bloom filter so that the false positive rate keeps neglicted. We herein generalize this approach by introducing the concept of foldin/unfolding along with a novel formulation of the problem: the key challenge consists in determining how a folding should be performed, namely the number of times that Bloom filter should be folded/unfolded and the reduction factor associated with each fold/ unfold. We formulate that as an off-line planing of the factorization of an integer (corresponding to the Bloom filter size) and further proposed directions for optimising the dynamic folding/unfolding of a Bloom filter.

Equipe: mim
Collaboration: SRI


@techreport {
title="{Folding and Unfolding Bloom Filters - an Off-line Planing and on Line-Optimisation}",
author="F. Sailhan and M. Stehr",
institution="{CEDRIC laboratory, CNAM-Paris, France}",