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.

Search Publications by:

Search Title, Abstract, Conference, Citation, Keyword or Author
Displaying 26 - 38 of 38

A New Analysis of the False-Positive Rate of a Bloom Filter

October 15, 2010
Author(s)
Ken Christensen, Allen L. Roginsky, Miguel Jimeno
A Bloom filter is a space-efficient data structure used for probabilistic set membership testing. When testing an object for set membership, a Bloom filter may give a false positive. The analysis of the false positive rate is key to understanding the Bloom

A Two-Tier Bloom Filter to Achieve Faster Membership Testing

March 27, 2008
Author(s)
Miguel Jimeno, K Christensen, Allen L. Roginsky
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