CFP last date
20 May 2024
Call for Paper
June Edition
IJCA solicits high quality original research papers for the upcoming June edition of the journal. The last date of research paper submission is 20 May 2024

Submit your paper
Know more
The week's pick
Responsive image
Enhancing Privacy Preservation: Multi-Attribute Protection with P-Sensitive K-Anonymity

Twinkle Patel Kiran Amin
Random Articles
Reseach Article

Artificial Immune System for Bloom filter Optimization

by Arulanand Natarajan, Swathy Priyadharsini P, Subramanian S
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 41 - Number 8
Year of Publication: 2012
Authors: Arulanand Natarajan, Swathy Priyadharsini P, Subramanian S
10.5120/5562-7641

Arulanand Natarajan, Swathy Priyadharsini P, Subramanian S . Artificial Immune System for Bloom filter Optimization. International Journal of Computer Applications. 41, 8 ( March 2012), 26-32. DOI=10.5120/5562-7641

@article{ 10.5120/5562-7641,
author = { Arulanand Natarajan, Swathy Priyadharsini P, Subramanian S },
title = { Artificial Immune System for Bloom filter Optimization },
journal = { International Journal of Computer Applications },
issue_date = { March 2012 },
volume = { 41 },
number = { 8 },
month = { March },
year = { 2012 },
issn = { 0975-8887 },
pages = { 26-32 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume41/number8/5562-7641/ },
doi = { 10.5120/5562-7641 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:29:05.104490+05:30
%A Arulanand Natarajan
%A Swathy Priyadharsini P
%A Subramanian S
%T Artificial Immune System for Bloom filter Optimization
%J International Journal of Computer Applications
%@ 0975-8887
%V 41
%N 8
%P 26-32
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Bloom filter is a probabilistic and space efficient data structure designed to check the membership of an element in a set. The trade-off to use Bloom filter may have configurable risk of false positives. The percentages of a false positive can be made low if the hash bit map is sufficiently massive. Spam is an unsolicited or irrelevant message sent on the internet to an outsized range of users or newsgroup. A spam word may be a list of well-known words that usually appear in spam mails. In the proposed system, Bin Bloom Filter (BBF) groups the words into number of bloom filters that have different false positive rates primarily based on the weights of the spam words. Clonal Selection Algorithm is one of the methods in Artificial Immune System (AIS) involved with computational methods inspired by the process of the biological immune system. This paper demonstrates the CSA algorithm for minimizing the total membership invalidation cost of the BBF which finds the optimal false positive rates and number of elements to be stored in bloom filters of Bin. The experimental results demonstrate the application of CSA in BBF and compare the results with Genetic Algorithm (GA).

References
  1. Bloom B, "Space/time tradeoffs in hash coding with allowable errors", Communications of the ACM, 13, 1970, pp. 422–426.
  2. Mullin J. K, "Optimal Semijoins for Distributed Database Systems", IEEE Trans. Software Eng. , 16, 1990, pp. 558-560.
  3. Mackert L. F. and Lohman G. M. , "Optimizer Validation and Performance Evaluation for Distributed Queries", Proc. 12th Int'l Conf. Very Large Data Bases (VLDB), 1986, 149-159.
  4. Broder A and Mitzenmacher M. "Network Applications of Bloom Filters: A Survey", Internet Math. , 1(4), 2005, pp. 485-509.
  5. Kubiatowicz J Bindel D, Chen, Y Czerwinski S, Eaton P, and Geels D, "Oceanstore: An Architecture for Global-Scale Persistent Storage," ACM SIGPLAN Notices, 35(11), 2000, pp. 190-201.
  6. Li J, Taylor J, Serban L, and Seltzer M, "Self-Organization in Peer-to-Peer System", Proc. ACM SIGOPS, 2002.
  7. Cuena-Acuna F. M, Peery C,Martin R. P, and Nguyen T. D, PlantP: "Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities", Proc. 12th IEEE Int'lSymp. High Performance Distributed Computing, 2003, pp. 236-249.
  8. Chen, H, Jin, H, Chen, L, Liu, Y and Ni, L. , "Optimizing Bloom Filter Settings in Peer-to-Peer Multi-keyword Searching", IEEE Transactions on Knowledge and Data Engineering, 2011, Vol. PP. No. 99, pp. 1 – 1.
  9. Rhea S. C and Kubiatowicz J, "Probabilistic Location and Routing", Proc. IEEE INFOCOM, 2004, 1248-1257.
  10. Hodes T. D, Czerwinski S. E, and Zhao B. Y, "An Architecture for Secure Wide Area Service Discovery", Wireless Networks, vol. 8, nos. 2/3, 2002, pp. 213-230.
  11. Reynolds P and Vahdat A, "Efficient Peer-to-Peer Keyword Searching", Proc. ACM Int'l Middleware Conf. , 2003, pp. 21-40.
  12. Bauer D, Hurley P, Pletka R, and Waldvogel M, "Bringing Efficient Advanced Queries to Distributed Hash Tables", Proc. IEEE Conf. Local Computer Networks, 2004, pp. 6-14.
  13. Fan L, Cao P, Almeida J, and Broder A, "Summary Cache: A Scalable Wide Area Web Cache Sharing Protocol", IEEE/ACM Trans. Networking, Vol. 8 No. 3, 2000, pp. 281-293.
  14. Peter C. D and Panagiotis M, "Bloom Filters in Probabilistic Verification", Proc. Fifth Int'l Conf. Formal Methods in Computer- Aided Design, 2004, pp. 367-381.
  15. Jin C, Qian W, and Zhou A, Analysis and Management of Streaming Data: A Survey, J. Software, 15(8), 2004, 1172-1181.
  16. Deng F and Rafiei D, "Approximately Detecting Duplicates for Streaming Data Using Stable Bloom Filters", Proc. 25th ACMSIGMOD, 2006, pp. 25-36.
  17. Bonomi F, Mitzenmacher M, Panigrahy R, Singh S, andVarghese G, "Beyond Bloom Filters: From Approximate Membership Checks to Approximate State Machines", Proc. ACM SIGCOMM, 2006 , pp. 315-326.
  18. Li K and Zhong Z, "Fast Statistical Spam Filter by Approximate Classifications", Proc. Joint Int'l Conf. Measurement and Modeling of Computer Systems, SIGMETRICS/Performance, 2006, pp. 347-358.
  19. Mitzenmacher M, "Compressed Bloom Filters", IEEE/ACM Trans. Networking, 10(5) 2002, pp. 604-612.
  20. Kirsch A and Mitzenmacher M, "Distance-Sensitive Bloom Filters", Proc. Eighth Workshop Algorithm Eng. and Experiments (ALENEX '06), 2006.
  21. Kirsch A and Mitzenmacher M, "Building a Better Bloom Filter, Technical Report" tr-02-05. pdf, Dept. of Computer Science, Harvard Univ,2006.
  22. Kumar A, Xu J, Wang J, Spatschek O, and Li L, "Space-Code Bloom Filter for Efficient Per-Flow Traffic Measurement", Proc. 23rd IEEE INFOCOM, 2004, pp. 1762-1773.
  23. Cohen S and Matias Y, "Spectral Bloom Filters", Proc. 22nd ACM SIGMOD, 2003, pp. 241-252.
  24. Laufer R. P, Velloso P. B, and Duarte O. C. M. B, "Generalized Bloom Filters", Technical Report Research Report GTA-05-43, Univ. of California, Los Angeles (UCLA), 2005.
  25. Chazelle B, Kilian J, Rubinfeld R, and Tal A, "The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables", Proc. Fifth Ann. ACM-SIAM Symp. Discrete Algorithms (SODA), 2004, pp. 30-39.
  26. Hao F, Kodialam M, and Lakshman T. V, "Building High Accuracy Bloom Filters Using Partitioned Hashing", Proc. SIGMETRICS/Performance, 2007, pp. 277-287.
  27. Paynter, M and Kocak, T, "Fully pipelined bloom filter architecture", Communications Letters, IEEE, 2008, Vol. 12, No. 11, pp. 855 - 857
  28. Deke Guo, Jie Wu, Honghui Chen, Ye Yuan and Xueshan Luo, "The Dynamic Bloom Filters", IEEE Transactions on Knowledge and Data Engineering, 2010,Vol. 22 No. 1, pp. 120 – 123.
  29. L. N. De Castro and F. J. Von Zuben (2002), "Learning and Optimization Using the Clonal Selection Principle", IEEE Transactions on Evolutionary Computation , 6(3) 239 – 251.
  30. Xie K. , Min Y. , Zhang D. , Wen J. , Xie G. & Wen J, "Basket Bloom Filters for Membership Queries", Proceedings of IEEE Tencon'05,2005, pp. 1-6.
  31. Berek, C. and Ziegner, M. "The Maturation of the Immune Response", Immunology Today, Vol. 14, No. 8, pp. 400-402, 1993.
  32. Back, T. "Self-Adaptation in Genetic Algorithms", Proceedings of the First European Conference on Artificial Life, Paris, France, December 11-13, pp. 263–271, 1991.
Index Terms

Computer Science
Information Sciences

Keywords

Clonal Selection Method Bloom Filter Spam Filter False Positive Rate Hash Function

Powered by PhDFocusTM