Implementation of Improved Hash and Mapping Modified Low Power Parallel Bloom Filter Design

Implementation of Improved Hash and Mapping Modified Low Power Parallel Bloom Filter Design

K. Saravanan (Department of Electronics and Communication, Nehru Institute of Technology, Coimbatore, Tamil Nadu, India) and A. Senthilkumar (Department of Electrical and Electronics, Dr. Mahalingam College of Engineering and Technology, Pollachi, Tamil Nadu, India)
Copyright: © 2013 |Pages: 11
DOI: 10.4018/ijisp.2013100102


In this article, the authors present an investigation on bloom filters and introduce a new improved variant, which uses a secure modified hash function and suggested improved mapping scheme with an efficient parallel architecture. This novel architecture provides efficient, relatively fast membership querying and compact information representation with negligible false positive. This is relatively a low power and secure design with very less false positive ratio when compared with the traditional bloom filters. The design has been evaluated and tested using Xilinx 65 nm Virtex-5 field-programmable gate array as the target technology. The performance matrices are false positive ratio, power, speed and compactness.
Article Preview

1. 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.

2. 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

Complete Article List

Search this Journal:
Open Access Articles
Volume 13: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 12: 4 Issues (2018)
Volume 11: 4 Issues (2017)
Volume 10: 4 Issues (2016)
Volume 9: 4 Issues (2015)
Volume 8: 4 Issues (2014)
Volume 7: 4 Issues (2013)
Volume 6: 4 Issues (2012)
Volume 5: 4 Issues (2011)
Volume 4: 4 Issues (2010)
Volume 3: 4 Issues (2009)
Volume 2: 4 Issues (2008)
Volume 1: 4 Issues (2007)
View Complete Journal Contents Listing