Cover Query Base On Bloom Filter

Cover query plays an important role in maintaining consistency and integrity of the file in the distributed systems.At present,the cover query is mainly executed by the “tree-structure”,such as DST or R-Tree.However,when the number of the single node or nodes in that tree structure is surging,the data index will become very large.This will affect query efficiency because the query is generally limited to the global index's speed of this structure.Bloom Filter is widely used in databases,networks and distributed system,which can represent data set and support quick membership query.The query operation in the Bloom Filter is not directly dependent on the scale of data set.Therefore,with the increase of the data set,the query will not be instantly affected.Although it has a very high efficiency in dealing with discrete data's storage and query,it cannot support the storage of the range rules directly.However,the cover query demands the storage of range rules,thus using Bloom Filter to support cover query is a big challenge.In this paper,the main discovery is as follows:Owing to the Bloom Filter's failure to store the range rules directly,in order to support cover query,this paper designs a BFrange structure,which combines the Count Bloom Filter with the linked list effectively.To make the BFrange possible to store the range rules,the range rule is converted to several discrete prefixes and also proposing a prefix-code transformation algorithm that can transforms each prefix to a unique binary code.Besides,extensive simulations demonstrate that the BFrange can not only support exact cover query,but also make the query time independent of the number of the rules.Compared with the R-Tree,the query efficiency is greatly improved.In order to further improve the efficiency of the cover query,this paper proposes a range rule's classification algorithm which can convert the range rule into multiple elements such as <benchmark,prefix>.In addition,a hierarchical coding transformation algorithm is proposed which can convert each <benchmark,prefix>into a unique binary code.It is theoretically proven to find the uniqueness of the hierarchical coding transformation algorithm in this paper.Based on the hierarchical coding algorithm,the Hie-BFrange structure is designed to store the hierarchical range rules and support fast cover query.It is found that compared with the BFrange structure in extensive simulations,the Hie-BFrange can improve the efficiency of query and make it more convenient and faster for the user.