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 Power Management Proxy with a New Best-of-N Bloom Filter Design to Reduce False Positives

Published

Author(s)

Miguel Jimeno, Allen L. Roginsky, K Christensen

Abstract

Bloom filters are a probabilistic data structure used to evaluate set membership. A group of hash functions are used to map elements into a Bloom filter and to test elements for membership. In this paper, we propose using multiple groups of hash functions and selecting the group that generates the Bloom filter instance with the smallest number of set bits. We evaluate the performance of this new Best-of-N method using order statistics and an actual implementation. Our analysis shows that significant reduction in the probability of a false positive can be achieved. We also propose and evaluate a new method that uses a random number generator (RNG) to generate multiple hashes from one initial hash. This RNG method (motivated by a method from Kirsch and Mitzenmacher) makes the computational expense of the Best-of-N method very modest. The targe application is a power management proxy for P2P applications executing in a resource-constrained "SmartNIC."
Conference Dates
April 11-13, 2007
Conference Location
New Orleans, LA, USA
Conference Title
International Performance Computing and Communications Conference (IPCCC 2007)

Citation

Jimeno, M. , Roginsky, A. and Christensen, K. (2007), A Power Management Proxy with a New Best-of-N Bloom Filter Design to Reduce False Positives, International Performance Computing and Communications Conference (IPCCC 2007), New Orleans, LA, USA, [online], https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=50943 (Accessed December 15, 2024)

Issues

If you have any questions about this publication or are having problems accessing it, please contact reflib@nist.gov.

Created April 1, 2007, Updated October 12, 2021