Please use this identifier to cite or link to this item: https://doi.org/10.1109/TC.2011.108
Title: Locality-sensitive bloom filter for approximate membership query
Authors: Hua, Y.
Xiao, B.
Veeravalli, B. 
Feng, D.
Keywords: Approximate membership query
bloom filters
locality sensitive hashing
Issue Date: 2012
Source: Hua, Y., Xiao, B., Veeravalli, B., Feng, D. (2012). Locality-sensitive bloom filter for approximate membership query. IEEE Transactions on Computers 61 (6) : 817-830. ScholarBank@NUS Repository. https://doi.org/10.1109/TC.2011.108
Abstract: In many network applications, Bloom filters are used to support exact-matching membership query for their randomized space-efficient data structure with a small probability of false answers. In this paper, we extend the standard Bloom filter to Locality-Sensitive Bloom Filter (LSBF) to provide Approximate Membership Query (AMQ) service. We achieve this by replacing uniform and independent hash functions with locality-sensitive hash functions. Such replacement makes the storage in LSBF to be locality sensitive. Meanwhile, LSBF is space efficient and query responsive by employing the Bloom filter design. In the design of the LSBF structure, we propose a bit vector to reduce False Positives (FP). The bit vector can verify multiple attributes belonging to one member. We also use an active overflowed scheme to significantly decrease False Negatives (FN). Rigorous theoretical analysis (e.g., on FP, FN, and space overhead) shows that the design of LSBF is space compact and can provide accurate response to approximate membership queries. We have implemented LSBF in a real distributed system to perform extensive experiments using real-world traces. Experimental results show that LSBF, compared with a baseline approach and other state-of-the-art work in the literature (SmartStore and LSB-tree), takes less time to respond AMQ and consumes much less storage space. © 1968-2012 IEEE.
Source Title: IEEE Transactions on Computers
URI: http://scholarbank.nus.edu.sg/handle/10635/56513
ISSN: 00189340
DOI: 10.1109/TC.2011.108
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

31
checked on Dec 5, 2017

WEB OF SCIENCETM
Citations

25
checked on Nov 16, 2017

Page view(s)

36
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.