Method for inquiring and updating Bloom filter based on tree structure

Abstract

The invention discloses a method for inquiring and updating a Bloom filter based on a tree structure. The method comprises the following steps of: storing a data set which is in a certain scale or contains corresponding characteristic data in a tree Bloom filter; reading in the data set to be inquired or updated; inquiring and updating elements of the Bloom filter based on the tree structure; and outputting an inquiry and updating result. By applying the method disclosed by the invention, misjudgement probability can be greatly reduced, the time of an inquiry and updating operation is reduced, the expandability of the Bloom filter is enhanced, guarantee is provided for network data storage and inquiry by members of the data set, and the method can be applied to data member detection in the data set and can be widely applied to a database, a network and a distributed system. The method for inquiring and updating the Bloom filter based on the tree structure is characterized by comprising the following steps of: 1) storing a data set which is in a certain scale or contains corresponding characteristic data in a tree Bloom filter; 2) reading in the data set to be inquired or updated; 3) inquiring and updating elements of the Bloom filter based on the tree structure; and 4) outputting an inquiry and updating result. The method for inquiring and updating the Bloom filter based on the tree structure according to the claim 1 is characterized in that the step for inquiring and updating the Bloom filter based on the tree structure comprises: firstly: performing Hash calculation to the data members by using a Hash function; secondly: performing model operation to the obtained Hash value, obtaining a '1' position of a bit of a first layer position '1' at the next layer leaf node; thirdly: counting the bit which is configured as '1' before the bit already configured as '1', obtaining an insertion position of the leaf node at the next leaf node; fourthly: inquiring or updating the leaf node at the corresponding position according to the obtained index data at the Bloom filter at a middle layer; and fifthly: inquiring or updating the bit number configured as '1' before the corresponding bit of the uplink layer in the last layer, and finding out the corresponding counter in the last layer.

Description

technical field [0001] The invention relates to electronic computer network technology, in particular to a tree-structure-based Bloom filter query and update method. Background technique [0002] With the continuous progress of computer science, especially the rapid development of network technology, the growth of the network scale is changing with each passing day, which makes the data scale in the database and network is also increasing, and the rational use of network resources has become a new round of computer science research. challenge. Today, when the data flow in the network is becoming larger and larger, how to reasonably represent and find the relevant information of a data flow so as to process it correctly has become the core issue in the field of computer applications. [0003] The utilization rate of storage space, data set query and update efficiency are the focus of Bloom filter and related research, especially when network bandwidth resources are still pre...

AI Technical Summary

Problems solved by technology

[0007] The defects of the BloomingTree algorithm in logical indexing are as follows: figure 1 As shown in the 5th bit marked in , when the 4th bit position is "1", because the BloomingTree algorithm must determine the next layer according to whether the previous bit of the queried bit is "1" or "0". The position of the leaf node is set to "1", and now the previous bit of the 5th bit has changed from "0" to "1", but the leaf node of the next layer of the 5th bit does not correspond The occurrence of this situation will inevitably lead to misjudgment when querying, especially when the size of the data set increases and the number of insertion and deletion operations increases.

Images