PROJECT TITLE :

Multi-Granularity Locality-Sensitive Bloom Filter

ABSTRACT:

In many applications, like homeland security, image processing, social network, and bioinformatics, it's typically needed to support an approximate membership query (AMQ) to answer an issue like “is an (question) object q near to at least one in every of the objects within the given data set ?” However, existing techniques for processing AMQs need a key parameter, i.e., the distance price, to be defined in advance for the query processing. In this paper, we propose a unique filter, referred to as multi-granularity locality-sensitive Bloom filter (MLBF), that will process AMQs with multiple distance granularities. Specifically, the MLBF consists of 2 Bloom filters (BF), one is called basic multi-granularity locality-sensitive BF (BMLBF), and the other is called multi-granularity verification BF (MVBF). The BMLBF is employed to store the information objects. It adopts an alignable locality-sensitive hashing (LSH) operate family to support multiple granularities. The MVBF is employed to scale back the false positive rate of the MLBF. The false negative rate of the MLBF is reduced by applying AND-constructions followed by an OR-construction. Further, based on the MLBF structure, we counsel a additional area-effective variant, called the MLBF*, to more reduce space price. Theoretical analyses for estimating false positive/negative rates of the MLBF/MLBF* are given. Experiments using synthetic and real knowledge show that the theoretical estimates are quite accurate, and the MLBF/MLBF* technique can handle AMQs with low false positive and negative rates for multiple distance granularities.