Jimeno, M.
, Christensen, K.
and Roginsky, A.
(2008),
A Two-Tier Bloom Filter to Achieve Faster Membership Testing, IEEE Electronics Letters, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=51317
(Accessed April 23, 2024)
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
Secure .gov websites use HTTPS
A lock (
) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.
A Two-Tier Bloom Filter to Achieve Faster Membership Testing
Published
Author(s)
Miguel Jimeno, K Christensen,
Abstract
Testing for element membership in a Bloom Filter requires hashing of a test element (e.g., a string) and multiple look-ups 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.Citation
IEEE Electronics Letters
Volume
44
Pub Type
Journals
Download Paper
Keywords
Bloom filter, caching, probability distributions
Citation
Created March 26, 2008, Updated October 12, 2021