The Design And Implementation Of A Scalable Counting Bloom Filter

The representation and query of information is the core of most computer applications.For the past few years,with the development of information technology,the computer network has become an important information infrastructure of the human society and has penetrated into all fields.The interaction of the shared resources promotes to generate more data and information.With the rapid development of computer,the scale of dataset in the database,network and other applications is increasing exponentially.In the case of that information set is becoming more and more large and the dataset's access and representation is more and more difficult,how to represent large dataset,and accomplish the query of these large dataset become a challenging topic in academia at home and abroad.Bloom Filter is a data structure which can concise express static collection and support set members' subordinate query.It uses a bit string represent data set,and support elements' hash lookup at the expense of the acceptable misjudgment rate.In the database,network and distributed systems,bloom filter has been widely used.However,restricted by the basic attributes of bloom filters,the filter must estimate the size of the filter in advance according to the number of storage elements and the given misjudgment rate in the actual application.If a bloom filter still need to add new elements when the capacity of the filter reaches its maximum,then the misjudgment rate would increase,and the standard Bloom filter only support the representation of static collection,and not support the element's deletion.Therefore,with the dynamic growth of datasets,and accompanying elements' deletion,traditional Bloom filters will be encountered insurmountable difficulties.For this reason,this paper designs a new type of Scalable Counting Bloom filter(SCBF).SCBF can identify the elements in the collection by adding additional metadata,and can enhance the relationship between the elements and Bloom filter,and can accurately judge which element belong to which Bloom filter.Moreover,SCBF not only can support insertion operation of new elements,but also support reliable delete of existing elements.The main work is as follows.Meanwhile,add a reducing tightening ratio r to limit false positives in order to ensure that overall misjudgment rate under control.1)Implement dynamic extension.It presents a dynamic expansion plan based on Counting Bloom filter,which suggested a means of scalable Bloom filters by creating essentially a list of Bloom filters that act as one large Bloom filter.When greater capacity is desired,a new filter is added to the list.2)Achieve precise remove.Mixing remove and scalability of Bloom filter.It takes additional identification during additions and deletions in the form of a monotonically increasing integer to classify elements.This is used to easily determine the correct Bloom filter for an element and ensure that an element can be removed from the correct filter.3)System optimize.We optimize the extension scale of SCBF and track system operation by introducing memory and disk sequences,and provides protection of data consistency.The theory and experiment show that SCBF can well realize the dynamic extension and dynamic delete,on the realization of function is superior to other Bloom filter.Furthermore,after a lot of testing,this paper found the best parameters values,which can ensure the misjudgment rate of the system in a controllable range all the time,and the space overhead of SCBF under full load condition is slightly larger than under ideal condition.