Error Detection and Correction using Bloom Filters

Error Detection and Correction using Bloom Filters

  IJETT-book-cover  International Journal of Engineering Trends and Technology (IJETT)          
  
© 2017 by IJETT Journal
Volume-51 Number-3
Year of Publication : 2017
Authors : Battu Naveen, N.Pitcheswara Rao
DOI :  10.14445/22315381/IJETT-V51P226

Citation 

Battu Naveen, N.Pitcheswara Rao "Error Detection and Correction using Bloom Filters", International Journal of Engineering Trends and Technology (IJETT), V51(3),145-149 September 2017. ISSN:2231-5381. www.ijettjournal.org. published by seventh sense research group

Abstract
The Bloom filter a way of using hash transforms to determine set member-ship. Bloom filters find application wherever fast set membership tests on large data sets are required. Such applications include spell checking, differential file updating, distributed network caches, and textual analysis. It is a probabilistic method with a set error rate. Errors can only occur on the side of inclusion, a true member will never be reported as not belonging to a set, but some non-members may be reported as members. Bloom filters use hash transforms to compute a vector (the filter) that is preventative of the data set. Membership is tested by comparing the results of hashing on the potential members to the vector. In its simplest form the vector is composed of N elements, each a bit. An element is set if and only if some hash transform hashes to that location for some key. Figure 2 shows such a filter with m = 4 hash transforms and N = 8 bits.

Reference
[1] "Optimal false-positive-free bloom filter design for scalable multicast forwarding", IEEE/ACM Transactions on Networking, vol. 23, no. , pp. 1832-1845, Dec. 2015, doi:10.1109/TNET.2014.2342155.
[2] "The Bloom Paradox: When Not to Use a Bloom Filter", IEEE/ACM Transactions on Networking, vol. 23, no. , pp. 703-716, June 2015, doi:10.1109/TNET.2014.2306060.
[3] Jiangbo Qian, Qiang Zhu, Yongli Wang, "Bloom Filter Based Associative Deletion", IEEE Transactions on Parallel & Distributed Systems, vol. 25, no. , pp. 1986-1998, Aug. 2014, doi:10.1109/TPDS.2013.223.
[4] Joao Trindade, Teresa Vazao, "A Performance Evaluation of HRAN: A Hybrid Routing Protocol Using Bloom Filters for Wireless Mobile Ad Hoc Networks", 2013 IEEE 12th International Symposium on Network Computing and Applications, vol. 00, no. , pp. 139-142, 2012, doi:10.1109/NCA.2012.17.
[5] Gang Wang, Jing Liu, Xiao-Guang Liu, Guang-Jun Xie, Jun Lee, "K-Divided Bloom Filter Algorithm and Its Analysis", Future Generation Communication and Networking, vol. 01, no. , pp. 220-224, 2007, doi:10.1109/FGCN.2007.157.
[6] Yuh-Jzer Joung, An-Hsun Cheng, "Probabilistic file indexing and searching in unstructured peer-to-peer networks", , vol. 00, no. , pp. 9-18, 2004, doi:10.1109/CCGrid.2004.1336543.
[7] Hyesook Lim, Miran Shim, Jungwon Lee, "Name prefix matching using bloom filter pre-searching", 2015 ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS), vol. 00, no. , pp. 203-204, 2015, doi:10.1109/ANCS.2015.7110141.

Keywords
bloom filters, error, detection, correction.