Efficient Update Control of Bloom Filter Replicas in Large Scale Distributed Systems

Introduction To Bloom Filters

A standard Bloom filter (BF) (Bloom, 1970) is a lossy but space-efficient data structure to support membership queries within a constant delay. As shown in Figure 1, a BF includes k independent random hash functions and a vector B of a length of m bits. It is assumed that the BF represents a finite set S = {x₁, x₂,…,x_n} of n elements from a universe . The hash functions h_i(x), 1 ≤ i ≤ k, map the universe U to the bit address space [1,m], shown as follows,

Figure 1.

A Bloom filter with a bit vector of m bits, and k independent hash functions. When an element x is added into the set represented, all bits indexed by those hash functions are set to 1.

This notation facilitates the description of operations on the subset of addressed by the hash functions. For example, B[H(x)] = 1 represents the condition in which all the bits in B at the positions of h₁(x),…, and h_k(x) are 1. “Setting B[H(x)]” means that the bits at these positions in B are set to 1.

Representing the set S using a BF B is fast and simple. Initially, all the bits in B are set to 0. Then for each x ∈ S, an operation of setting B[H(x)] is performed. Given an element x, to check whether is in , one only needs to test whether B[H(x)] = 1. If no, then x is not a member of S; If yes, x is conjectured to be in S. Figure 1 shows the results after the element x is inserted into the Bloom filter.

A standard BF has two well-known properties that are described by the following two theorems.