Abstract Counting Bloom Filters (CBFs) are widely employed in many applications for fast membership queries. CBF works on dynamic sets rather than a static set via item insertions and deletions. CBF allows false positive, but not false negative. The Bh-Counting Bloom Filter (Bh-CBF) and Variable Increment Counting Bloom Filter (VI-CBF) are introduced to reduce the False Positive Probability (FPP), but they suffer from memory overhead and hardware complexity. In this paper, we proposed a multilevel optimization approach named as Veracious Bh-Counting Bloom Filter (VBh-CBF) and Veracious Variable Increment Counting Bloom Filter (VVI-CBF) by partitioning the counter vector into multiple levels to reduce the FPP

References

[1] Ali Q., A Flexible Design of Network Devices Using Reconfigurable Content Addressable memory, The international Arab Journal of Information technology, vol. 8, no. 3, pp. 235- 243, 2011.

[2] Almeida P., Baquero C., Preguica N., and Hutchison D., Scalable Bloom Filters, Information Processing Letters, vol. 101, no. 6, pp. 255-261, 2007.

[3] Bloom B., Space/Time Trade-Offs in Hash Coding with Allowable Errors, Communications of the ACM, vol. 13, no. 7, pp. 422-426, 1970.

[4] Bonomi F., Mitzenmacher M., Panigrahy R., Sushil S., and Varghese G., An Improved Construction for Counting Bloom Filters, in Proceeding of 14th conference on Annual European Symposium, Zurich, pp. 684-695, 2006.

[5] Bose P., Guo H., Kranakis E., Maheshwari A., Morin P., Morrison J., Smid M., and Tang Y., On the False-Positive Rate of Bloom Filters, Information Processing Letters, vol. 108, no. 4, pp. 210-213, 2008.

[6] Brindha P. and SenthilKumar A., Area Efficient Counting Bloom Filter (A-CBF) Design for NIDS, International Journal of Computer Applications, vol. 70, no. 4, pp.17-21, 2013.

[7] Brindha P. and SenthilKumar A., Network Intrusion Detection System: An Improved Architecture to Reduce False Positive Rate, Journal of Theoretical and Applied Information Technology, vol. 66, no. 2, pp.618-626, 2014.

[8] Brindha P., SenthilKumar A., and Mohanapriyaa V., Survey and Evaluation of D Flipflop for Low Power Counter Design Using Sub-Micron Technology, International Journal of Electronics Communication and Computer Engineering, vol. 4, no. 2, pp. 339-343, 2012.

[9] Broder A. and Mitzenmacher M., Network Application of Bloom Filter: A Survey, Internet Mathematics, vol. 1, no. 4, pp. 484- 509, 2004.

[10] Chazelle B., Kilian J., Rubinfeld R., and Tal A., The Bloomier Filter: an Efficient Data Structure for Static Support Lookup Tables, in Proceeding of 15th Annual ACM-SIAM Symp, On Discrete Algorithms, Philadelphia, pp. 30-39, 2004.

[11] Cohen S. and Matias Y., Spectral Bloom Filters, in Proceeding of the 2003 ACM SIGMOD international conference on Management of data, New York, pp.241-252, 2003.

[12] Deng F. and Rafiei D., Approximately Detecting Duplicates for Streaming Data Using Stable Bloom Filters, in Proceeding of the ACM SIGMOD Conference, New York, pp. 25-36, 2006.

[13] Fan L., Cao P., Almeida J., and Broder A., Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol, IEEE/ACM Transactions on Networking, vol. 8, no.3, pp. 281-293, 2000.

[14] Ficara D., DI Pietro A., Giordano S., Procissi G., and Vitucci F., Enhancing Counting Bloom Filters Through Huffman-Coded Multilayer Structures, IEEE/ACM Transactions on Networking, vol. 18, no. 6, pp. 1977-1987, 2010. 896 The International Arab Journal of Information Technology, Vol. 14, No. 6, November 2017

[15] Geravand S. and Ahmadi M., Bloom Filter Applications in Network Security: A State-of- the-Art Survey, Computer Networks, vol. 57, no. 18, pp. 4047-4064, 2013.

[16] Graham S., Bh Sequences, Progress in mathematics, vol. 138, pp. 431-449, 1996.

[17] Guo D., Liu Y., Li X., and Yang P., False Negative Problem of Counting Bloom Filter, IEEE Transactions on Knowledge and Data Engineering, vol. 22, no. 5, pp. 651-664, 2010.

[18] Huang K., Zhang J., Zhang D., Xie G., Salamatian K., Liu A., and Li W., A Multi- Partitioning Approach to Building Fast and Accurate Counting Bloom Filters, in Proceeding of 27th International Symposium on Parallel and Distributed Processing, Boston, pp. 1159-1170, 2013.

[19] Laufer R., Velloso P., and Duarte O., A Generalized Bloom Filter to Secure Distributed Network Applications, Computer Networks, vol. 55, no. 8, pp. 1804-1819, 2011.

[20] Li W., Huang K., Zhang D., and Qin Z., Accurate Counting Bloom Filter For Large Scale Data Processing, Mathematical Problems in Engineering, vol. 2013, pp. 1-11, 2013.

[21] Manjula G. and Brindha P., A Survey on Architectural Design of Bloom Filter for Signature Detection, International Journal of Engineering Research and Technology, vol. 2, no. 3, pp. 1-6, 2013.

[22] Martin G. and O Bryant K., Constructions of Generalized Sidon Sets, Journal of Combinatorial Theory, Series A, vol. 113, no. 4, pp. 591-607, 2006.

[23] Mitzenmacher M., Compressed Bloom Filters, IEEE/ACM Transactions on Networking, vol. 10, no. 5, pp. 604-612, 2002.

[24] Paynter M. and Kocak T., Fully Pipelined Bloom Filter Architecture, IEEE Communications Letters, vol. 12, no. 11, pp. 855-857, 2008.

[25] Rottenstreich O., Keslassy I., and Keslassy I., The Variable Increment Counting Bloom Filter, in Proceeding of IEEE INFOCOM, Orlando, pp. 1880-1888, 2012.

[26] Safi E., Moshovos A., and Veneris A., L- CBF: A Low-Power, Fast Counting Bloom Filter Architecture, IEEE Transactions on Very Large Scale Integration Systems, vol. 16, no. 6, pp. 628-638, 2008. Brindha Palanisamy has received her B.E. Degree in Electronics and Communication Engineering Anna University, Chennai in 2006 and M.E. Degree in VLSI DESIGN from Anna University, Coimbatore in 2009. She is currently doing her research under Anna University, Chennai. Her current research is on Network Intrusion Detection System. Currently she is working as Assistant Professor (Sr.Gr.) at Velalar College of Engineering and Technology, Erode, India. She has published 5 research papers in various international journals. Area of interest includes low power VLSI design, VLSI signal processing and Network Security. She is the life member of ISTE and IETE. SenthilKumar Athappan has received his B.E. Degree in Electrical and Electronics Engineering from PSG College of Technology in 1995 and M.E. Degree in VLSI Systems from Regional Engineering College (NIT), Trichy, in 2001. He completed Ph.D in the area of VLSI Signal Processing from Anna University, Chennai in 2009. Currently, he is the Professor and Head, Department of EIE, Dr. Mahalingam College of Engineering and Technology, Pollachi, India. He presented more than 30 papers in various national and international conferences. He published 13 papers in International Journals in the area of Low power VLSI design. His area of interest includes Embedded System, VLSI Signal Processing, and Industrial Automation.