Using the Power of Two Choices to Improve Bloom Filters

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...

Full description

Saved in:
Bibliographic Details
Published in:Internet mathematics 2007-01, Vol.4 (1), p.17-33
Main Authors: Lumetta, Steve, Mitzenmacher, Michael
Format: Article
Language:English
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c417t-c654c295668387f949aa6abab590cd8c4ea8fd9ddbe114182b8f63946ba792fc3
cites
container_end_page 33
container_issue 1
container_start_page 17
container_title Internet mathematics
container_volume 4
creator Lumetta, Steve
Mitzenmacher, Michael
description 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.
doi_str_mv 10.1080/15427951.2007.10129136
format article
fullrecord <record><control><sourceid>crossref_proje</sourceid><recordid>TN_cdi_projecteuclid_primary_oai_CULeuclid_euclid_im_1243430566</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1080_15427951_2007_10129136</sourcerecordid><originalsourceid>FETCH-LOGICAL-c417t-c654c295668387f949aa6abab590cd8c4ea8fd9ddbe114182b8f63946ba792fc3</originalsourceid><addsrcrecordid>eNqFkM1KAzEUhYMoWKuvIHmBqfmbTLKSOlgtFHTRrkMmk9iUmaYko6Vvb0pbt67u5XDOuZcPgEeMJhgJ9IRLRipZ4glBqMoSJhJTfgVGWDJWSCbEdd6zqTi6bsFdShuECJWyHIFqlfz2Cw5rCz_D3kYYHFzuA6zXwRub4BDgvN_F8GPhSxdCD2e-G2xM9-DG6S7Zh_Mcg9XsdVm_F4uPt3k9XRSG4WooDC-ZIbLkXFBROcmk1lw3uiklMq0wzGrhWtm2jcWYYUEa4TiVjDe6ksQZOgbPp978w8aawX6bzrdqF32v40EF7VW9WpzV8_C9woRRRlG-mxv4qcHEkFK07i-MkToCVBeA6ghQXQDm4PQU9FsXYq_3IXatGvShC9FFvTU-KfpPxy8yKnec</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Using the Power of Two Choices to Improve Bloom Filters</title><source>Project Euclid</source><creator>Lumetta, Steve ; Mitzenmacher, Michael</creator><creatorcontrib>Lumetta, Steve ; Mitzenmacher, Michael</creatorcontrib><description>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.</description><identifier>ISSN: 1542-7951</identifier><identifier>EISSN: 1944-9488</identifier><identifier>DOI: 10.1080/15427951.2007.10129136</identifier><language>eng</language><publisher>A.K. Peters</publisher><ispartof>Internet mathematics, 2007-01, Vol.4 (1), p.17-33</ispartof><rights>Copyright Taylor &amp; Francis Group, LLC 2007</rights><rights>Copyright 2007 A K Peters, Ltd.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c417t-c654c295668387f949aa6abab590cd8c4ea8fd9ddbe114182b8f63946ba792fc3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,777,781,882,922,4010,27904,27905,27906</link.rule.ids></links><search><creatorcontrib>Lumetta, Steve</creatorcontrib><creatorcontrib>Mitzenmacher, Michael</creatorcontrib><title>Using the Power of Two Choices to Improve Bloom Filters</title><title>Internet mathematics</title><description>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.</description><issn>1542-7951</issn><issn>1944-9488</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2007</creationdate><recordtype>article</recordtype><recordid>eNqFkM1KAzEUhYMoWKuvIHmBqfmbTLKSOlgtFHTRrkMmk9iUmaYko6Vvb0pbt67u5XDOuZcPgEeMJhgJ9IRLRipZ4glBqMoSJhJTfgVGWDJWSCbEdd6zqTi6bsFdShuECJWyHIFqlfz2Cw5rCz_D3kYYHFzuA6zXwRub4BDgvN_F8GPhSxdCD2e-G2xM9-DG6S7Zh_Mcg9XsdVm_F4uPt3k9XRSG4WooDC-ZIbLkXFBROcmk1lw3uiklMq0wzGrhWtm2jcWYYUEa4TiVjDe6ksQZOgbPp978w8aawX6bzrdqF32v40EF7VW9WpzV8_C9woRRRlG-mxv4qcHEkFK07i-MkToCVBeA6ghQXQDm4PQU9FsXYq_3IXatGvShC9FFvTU-KfpPxy8yKnec</recordid><startdate>20070101</startdate><enddate>20070101</enddate><creator>Lumetta, Steve</creator><creator>Mitzenmacher, Michael</creator><general>A.K. Peters</general><general>A K Peters, Ltd</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20070101</creationdate><title>Using the Power of Two Choices to Improve Bloom Filters</title><author>Lumetta, Steve ; Mitzenmacher, Michael</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c417t-c654c295668387f949aa6abab590cd8c4ea8fd9ddbe114182b8f63946ba792fc3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2007</creationdate><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Lumetta, Steve</creatorcontrib><creatorcontrib>Mitzenmacher, Michael</creatorcontrib><collection>CrossRef</collection><jtitle>Internet mathematics</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Lumetta, Steve</au><au>Mitzenmacher, Michael</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Using the Power of Two Choices to Improve Bloom Filters</atitle><jtitle>Internet mathematics</jtitle><date>2007-01-01</date><risdate>2007</risdate><volume>4</volume><issue>1</issue><spage>17</spage><epage>33</epage><pages>17-33</pages><issn>1542-7951</issn><eissn>1944-9488</eissn><abstract>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.</abstract><pub>A.K. Peters</pub><doi>10.1080/15427951.2007.10129136</doi><tpages>17</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1542-7951
ispartof Internet mathematics, 2007-01, Vol.4 (1), p.17-33
issn 1542-7951
1944-9488
language eng
recordid cdi_projecteuclid_primary_oai_CULeuclid_euclid_im_1243430566
source Project Euclid
title Using the Power of Two Choices to Improve Bloom Filters
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-17T16%3A26%3A11IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_proje&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Using%20the%20Power%20of%20Two%20Choices%20to%20Improve%20Bloom%20Filters&rft.jtitle=Internet%20mathematics&rft.au=Lumetta,%20Steve&rft.date=2007-01-01&rft.volume=4&rft.issue=1&rft.spage=17&rft.epage=33&rft.pages=17-33&rft.issn=1542-7951&rft.eissn=1944-9488&rft_id=info:doi/10.1080/15427951.2007.10129136&rft_dat=%3Ccrossref_proje%3E10_1080_15427951_2007_10129136%3C/crossref_proje%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c417t-c654c295668387f949aa6abab590cd8c4ea8fd9ddbe114182b8f63946ba792fc3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true