Two-tier Bloom filter to achieve faster membership testing

Access Full Text

Two-tier Bloom filter to achieve faster membership testing

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
Electronics Letters — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

© The Institution of Engineering and Technology
Published

Testing for element membership in a Bloom filter requires hashing of a test element (e.g. a string) and multiple lookups in memory. A design of a new two-tier Bloom filter with on-chip hash functions and cache is described. For elements with a heavy-tailed distribution for popularity, membership testing time can be significantly reduced.

Inspec keywords: testing; cache storage; filters

Other keywords: cache functions; heavy-tailed distribution; two-tier bloom filter; on-chip hash functions; memory lookup times; faster membership testing

Subjects: Memory circuits; Filters and other networks; Semiconductor storage

References

    1. 1)
      • A. Broder , M. Mitzenmacher . Network applications of Bloom filters: a survey. Internet Math. , 4 , 485 - 509
    2. 2)
      • Chu, J., Labonte, K., Levine, B.: `Availability and locality measurements of peer-to-peer file systems', Proc. of SPIE, July 2002, 4868, in ‘ITCom: scalability and traffic control in ip networks’.
    3. 3)
    4. 4)
      • Mitzenmacher, M.: `Compressed Bloom filters', Proc. 20th ACM Symp. on PODC, August 2001, p. 144–150.
    5. 5)
      • Breslau, L., Cao, P., Fan, L., Phillips, G., Shenker, S.: `Web caching and Zipf-like distributions: Evidence and implications', Proc. IEEE INFOCOM, April 1999, p. 126–134.
    6. 6)
      • S. Dharmapurikar , P. Krishnamurthy , D.E. Taylor . Longest prefix matching using Bloom filters. IEEE/ACM Transactions on Networking , 2 , 397 - 409
    7. 7)
      • Fan, L., Cao, P., Almeida, J., Broder, A.: `Summary cache: a scalable wide area web cache sharing protocol', ACM SIGCOMM, 1998, p. 254–265.
http://iet.metastore.ingenta.com/content/journals/10.1049/el_20080081
Loading

Related content

content/journals/10.1049/el_20080081
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading