Skip to main content
U.S. flag

An official website of the United States government

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, Allen L. Roginsky

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

Keywords

Bloom filter, caching, probability distributions

Citation

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 September 27, 2023)
Created March 26, 2008, Updated October 12, 2021