Augmented Array based Efficient Fill Ratio Estimation in a Bloom Filter

Analysing patterns/trends and associations from het-erogeneous data coming at varied speeds and formats require data structures which can handle large and dynamic data efficiently. Bloom Filter (BF), a probabilistic data structure, can be considered as one of the alternatives as it is space efficient and handles membership query effectively. To accommodate the dynamic data sets in the BF when ever the Fill Ratio (FR) exceeds the defined limits, two major approaches have been discussed in the literature: increasing the number of BFs as the data increases and refreshing the existing BF by deleting the staled data. In this paper, a novel approach motivated from Double probing named (DH-FRP) has been proposed to compute FR using augmented array to sample bit locations from parent BF. The augmented array keeps track of the sampled bit values at any given time and stores at contiguous locations for effcient bit counting and FR calculation. Markov Bound has been used to determine whether to recompute the step size or not. Since the rate of dynamic data coming from various sources may be uniform or non uniform, both cases have been considered and FR has been calculated for standard BF and Counting BF. It has been experimentally proved that the proposed scheme outperforms the given state-of-art techniques in terms of FR calculation time and accuracy.

I. Introduction

With the exponential growth of data generation resources which include sensors, social media, on-line transactions, recommender systems, etc., bulk data storage and analytic is a challenging task [1]. Bloom Filter[BF] is a probabilistic model which helps to answer approximate membership query in constant time. BF stores the entire data in an array of m bits by hashing the entire input through independent and uniform hash functions. Many advance variants of BF have been designed to solve problems like, duplicate detection, outlier detection, time-range query, etc. in streaming data.