A Bloom Filter Framework Based On Shifting

As computing technology develops,there is an increase in the number of data needed to retract from the date set for communication propose and other applications preforming similar functions.Today' s community are in need of a tighter data struc-ture to use for processing such massive amount of of data sets.In this paper,we will be focusing on how to improve response time for set query.As we know,set queries serves as a foundation for all computing system and applications,therefore,the efficiency of set queries directly affect the efficiency to process data sets.In a set queries,efficiency mainly are determined by three factors:memory access,query time and correct rate.Traditionally,massive data set are processed by Bloom Filter.in this paper,we combined the classical Bloom Filter and various improved version of Bloom Filter to create a brand new data structure,and we named this model Shifting Bloom Filter.This structure can be used to store data,and can also be used to process set query.Because of the ShBF are mainly going to be utilized for set related functions,therefore we will be focusing on typical set functions when testing for performances.To demonstrate our data structure' s effectiveness and how to operate the system,we have selected three most common set query types,they are:Membership queries,Association Queries and Multiplicity Queries.The innovation about ShBF is that it using shifting to remember more data.When a typical BF process query,a word space is used every time for data access,however,only one bit is needed during such procedure.We call those extra bites within that word used Shifting.The ShBF uses Shifting of an element to code more data into it,therefore achieve optimization of BF.If there are more data to be added besides what was already there within the ele-ment,ShBF adopts a totally different way of process then earlier models of BF.Within earlier BF structure,the algorithm demands the applications to distribute more memory when in need of store extra data,but ShBF consider to have those extra data stored into Shiftings of that element.In this paper,ShBF provides three variations with slight differences aiming to serve three different situations,those performances will be compared to classical BF.In the testing stage,we use a collection of simulation data and real network data to assess the classical BF agist ShBF to prove its performance advantages under memory usage,calculation quantity and correct rate.