Searching method based on classified file BloomFilter structure

Abstract

This invention discloses one requiring method based on bloom filter structure, which divides different prices of different elements into different sub set and through looking each sub set lowest failure rate relationship establishes each sub set lowest positive rate to represent set integration lowest requirement invalid cost aim function. The invention uses category function step inherit formula to get each optimized Hars function number to fulfill set mapping and finding to vector.

Description

technical field [0001] The invention is a query method based on a graded Bloom Filter structure that supports set query starting from cost, belongs to the technical field of distributed computing, and in particular relates to applications that generate a large amount of data in a distributed system and require interactive query. Background technique [0002] In recent years, with the rapid development of computers, the scale of data collections in databases, networks and other applications has grown geometrically. Collection element queries are the most common operations on data collections. When the collection becomes larger and larger, access and representation become more and more difficult. How to represent large data collections and complete queries under large data collections has become a challenge for academic circles at home and abroad. It is an urgent need to design a simplified data structure representation and support data query of large collections. [0003] B...

AI Technical Summary

Problems solved by technology

[0009] However, the current Bloom Filter structure does not consider the query cost of the collection. They think that the I / O operation cost of the collection elements is the same when querying, but in practice, the elements in the collection are invalid due to query (false positives occur), Query invalidation cost of elements Due to the different roles and positions of elements in the collection, the extra operation cost when querying invalid is not the same

Because the previous Bloom Filter structure did not consider the query cost, they treated the elements in the collection uniformly, assigned the same number of hash mapping functions to each element, and the query failure rate of each element was the same, resulting in a comparison of the overall query cost of the collection. high

The lack of query cost consideration and the lack of differentiated treatment of elements are common drawbacks in the current Bloom Filter, which often consumes more resources in current practical applications.

Images