Article Preview
Top1. Introduction
Bloom filter is an efficient data structure design and compact information representation technique for membership queries (Burton Bloom, 1970). Initially bloom filters were utilized in intelligent dictionaries and spell checking applications. Its ability for dynamic membership querying and compact information representation attracted recent researches. Different variants of bloom filter have been emerged and still it requires optimization for efficient utilization in diverse applications. It consists of two sub blocks namely hashing block and mapping block. Bloom filter is used to store any set of elements in a portable manner by performing multiple hash functions on each elements in the set and store its hashed value in the storage vector array. After programming the bloom filter, it can be used to query the programmed or inserted elements. The query result may be sometimes false positive but never false negative. It is interesting to note that the computational time of the bloom filter is independent of the number of elements stored but it will affect the false positive ratio (FPR) of the result. Universal H3 hash function is widely used in almost all the bloom filters for its simplicity. Since bloom filters are widely utilized in security applications, the hashing scheme used in bloom filters has to provide random and secure mapping to prevent various attacks especially during wireless transmission of entire bloom filter information. In order to improve the security in bloom filters, we step into research to provide suitable modifications in the hashing and mapping units. The functional block diagram of a standard bloom filter mapping is shown in Figure 1. Bloom filter has to be programmed first by proper element insertion. Hence optimization in terms of power, speed, FPR and scalability can be achieved by proper design principles also.
Figure 1. Functional block diagram of bloom filter mapping
In the proposed design, we model a power efficient bloom filter with bit split parallel architecture which uses a modified hash function and efficient mapping scheme. The rest of the article is organized as follows. Survey of bloom filter concept and its applications are discussed in Section 2. Mathematical modeling for bloom filters in Section 3. Section 4 gives the concept of proposed bloom filter. Section 5 gives the discussions on experimental results and Section 6 gives conclusion.
Top2. Literature Survey
Bloom filter was introduced in Burton (1970) by Burton Bloom during 1970. Recently the research community realized the importance of bloom filter called standard bloom filter (SBF) and started proposing various design optimization to it for various scientific applications. The input elements are hashed and the hashed values are used to set the corresponding bit vector representing its membership. SBF was intensively investigated by the research community to propose various variants of bloom filter and its concept as the base for every proposed model. SBF introduced the wise space compatibility scenario which remains as a historic reference for new variants and it is seen that space compatibility is not compromised for the sake of any attributes during the development of new variants. In SBF, It is not possible to delete a member stored. For deleting a particular member the bits set by its hashed value has to be reset and it is possible that few of those bits may be set for some other member and its membership will be disturbed. Hence to overcome this, counting bloom filter (L. fan 2000) was proposed. In CBF, for every bit in the ‘m’ bit vector, a counter is used. Addition and deletion of members are possible by incrementing and decrementing the corresponding counters respectively. Counting bloom filter provides scalability in terms of design to perform parallel processing and pipeline processing Figure 2 shows the general architecture of CBF.
Figure 2. General architecture of CBF