Implementation Of “Bloom Filter” Using Cam Based Structure

Suravarapu Anusha, M Srihari, N Nagendra Kumar


content addressable memory (CAM) employing a new algorithm for associativity between the input tag and the corresponding address of the output data. The proposed architecture is based on a recently developed sparse clustered network using binary connections that on-average eliminates most of the parallel comparisons per- formed during a search. Therefore, the dynamic energy consumption of the proposed design is significantly lower compared with that of a conventional low-power CAM design. Given an input tag, the proposed architecture computes a few possibilities for the location of the matched tag and performs the comparisons on them to locate a single valid match.

Bloom filters (BFs) provide a fast and efficient way to check whether a given element belongs to a set. The BFs are used in numerous applications, for example, in communications and networking. There is also ongoing research to extend and enhance BFs and to use them in new scenarios. Reliability is becoming a challenge for advanced electronic circuits as the number of errors due to manufacturing variations, radiation, and reduced noise margins increase as technology scales. In brief, it is shown that BFs can be used to detect and correct errors in their associated data set. This allows a synergetic reuse of existing BFs to also detect and correct errors. The proposed scheme Content-addressable memory (CAM) is a special type of computer memory used in certain very-high-speed searching applications. It is also known as associative memory, associative storage, or associative array, although the last term is more often used for a programming data structure. It compares input search data (tag) against a table of stored data, and returns the address of matching data (or in the case of associative memory, the matching data). Several custom computers, like the Goodyear STARAN, were built to implement CAM, and were designated associative computers.


Bloom filters (BFs), error correction, soft errors.


B. Bloom, “Space/time tradeoffs in hash coding with allowable errors,” Commun. ACM, vol. 13, no. 7, pp. 422–426, 1970.

A. Broder and M. Mitzenmacher, “Network applications of bloom filters: A survey,” in Proc. 40th Annu. Allerton Conf., Oct. 2002, pp. 636–646.

A. Moshovos, G. Memik, B. Falsafi, and A. Choudhary, “Jetty: Filtering snoops for reduced energy consumption in SMP servers,” in Proc. Annu. Int. Conf. High-Perform. Comput. Archit., Feb. 2001, pp. 85–96.

C. Fay et al., “Bigtable: A distributed storage system for structured data,” ACM TOCS, vol. 26, no. 2, pp. 1–4, 2008.

F. Bonomi, M. Mitzenmacher, R. Panigrahy, S. Singh, and G. Varghese, “An improved construction for counting bloom filters,” in Proc. 14th Annu. ESA, 2006, pp. 1–12.

M. Mitzenmacher, “Compressed bloom filters,” in Proc. 12th Annu. ACM Symp. PODC, 2001, pp. 144–150.

M. Mitzenmacher and G. Varghese, “Biff (Bloom Filter) codes: Fast error correction for large data sets,” in Proc. IEEE ISIT, Jun. 2012, pp. 1–32.

S. Elham, A. Moshovos, and A. Veneris, “L-CBF: A low-power, fast counting Bloom filter architecture,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 16, no. 6, pp. 628–638, Jun. 2008.

T. Kocak and I. Kaya, “Low-power bloom filter architecture for deep packet inspection,” IEEE Commun. Lett., vol. 10, no. 3, pp. 210–212, Mar. 2006.

S. Dharmapurikar, H. Song, J. Turner, and J. W. Lockwood, “Fast hash table lookup using extended bloom filter: An aid to network processing,” in Proc. ACM/SIGCOMM, 2005, pp. 181–192.

Full Text: PDF [Full Text]


  • There are currently no refbacks.

Copyright © 2013, All rights reserved.|

Creative Commons License
International Journal of Science Engineering and Advance Technology is licensed under a Creative Commons Attribution 3.0 Unported License.Based on a work at IJSEat , Permissions beyond the scope of this license may be available at