TY - JOUR

T1 - Using the power of two choices to improve bloom filters

AU - Lumetta, Steve

AU - Mitzenmacher, Michael

N1 - Funding Information:
Acknowledgements. The first author was supported in part by NSF grant ACI-9984492. The second author was supported in part by NSF grant CCR-0121154 and a grant from Cisco.

PY - 2007/1/1

Y1 - 2007/1/1

N2 - We consider the combination of two ideas from the hashing literature: the power of two choices and Bloom filters. Specifically, we show via simulations that, in comparison with a standard Bloom filter, using the power of two choices can yield modest reductions in the false positive probability using the same amount of space and more hashing. While the improvements are sufficiently small that they may not be useful in most practical situations, the combination of ideas is instructive; in particular, it suggests that there may be ways to obtain improved results for Bloom filters while using the same basic approach they employ, as opposed to designing new, more complex data structures for the problem.

AB - We consider the combination of two ideas from the hashing literature: the power of two choices and Bloom filters. Specifically, we show via simulations that, in comparison with a standard Bloom filter, using the power of two choices can yield modest reductions in the false positive probability using the same amount of space and more hashing. While the improvements are sufficiently small that they may not be useful in most practical situations, the combination of ideas is instructive; in particular, it suggests that there may be ways to obtain improved results for Bloom filters while using the same basic approach they employ, as opposed to designing new, more complex data structures for the problem.

UR - http://www.scopus.com/inward/record.url?scp=79953769032&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79953769032&partnerID=8YFLogxK

U2 - 10.1080/15427951.2007.10129136

DO - 10.1080/15427951.2007.10129136

M3 - Article

AN - SCOPUS:79953769032

SN - 1542-7951

VL - 4

SP - 17

EP - 33

JO - Internet Mathematics

JF - Internet Mathematics

IS - 1

ER -