tag:blogger.com,1999:blog-8890204.post1915354351308425701..comments2024-03-10T05:26:42.148-04:00Comments on My Biased Coin: Hash Table with Preemptive Bloom FilterMichael Mitzenmacherhttp://www.blogger.com/profile/06738274256402616703noreply@blogger.comBlogger13125tag:blogger.com,1999:blog-8890204.post-56911006463194471382009-03-24T13:15:00.000-04:002009-03-24T13:15:00.000-04:00access-filtered hash tablepre-screened hash tablem...access-filtered hash table<BR/><BR/>pre-screened hash table<BR/><BR/>mostly-positive hash table<BR/>(humor: generally-positive hash table)<BR/><BR/>...<BR/><BR/>btw: I've been spending too much time thinking about bloom filters lately. I'd love to chat @ NSDI or at the sigcomm TPC meeting, if you're going to be at either.David Andersenhttps://www.blogger.com/profile/03996590425188586871noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-11822897025098881102009-03-03T04:42:00.000-05:002009-03-03T04:42:00.000-05:00Naming things like this puts up barriers to entry,...Naming things like this puts up barriers to entry, thus hurting outsiders. It does make things easier for the crowd that knows the language, but the cost is too high. When we teach, we should just say "This is a Bloom Filter; it is named after a person and has nothing to do with flowers; here are some uses."Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-14544682681819290462009-02-28T12:24:00.000-05:002009-02-28T12:24:00.000-05:00...and hashbrowns....and hashbrowns.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-45680863148468251122009-02-28T12:22:00.000-05:002009-02-28T12:22:00.000-05:00bloomin' onionbloomin' onionAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-60460889783504622392009-02-28T08:32:00.000-05:002009-02-28T08:32:00.000-05:00Blash table!Blash table!Greg Morrisetthttps://www.blogger.com/profile/14071364309433455218noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-56768931107916562932009-02-27T15:23:00.000-05:002009-02-27T15:23:00.000-05:00A blushing filter?A blushing filter?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-30752824590165718822009-02-27T15:12:00.000-05:002009-02-27T15:12:00.000-05:00Anon 2: I agree in spirit that really this is jus...Anon 2: I agree in spirit that really this is just "using a Bloom filter", but it's helpful to give it a name so people will stop feeling the need to describe it. Although perhaps just a standard sentence, "We use a Bloom filter on the keys of the hash table to preempt most unsuccessful searches" should suffice.<BR/><BR/>Anon 6: Blooming is unsatisfactory. Bloom is the man's name. We don't call it a Karping reduction, even though that sounds kind of funny too.Michael Mitzenmacherhttps://www.blogger.com/profile/02161161032642563814noreply@blogger.comtag:blogger.com,1999:blog-8890204.post-32990910464312391192009-02-27T12:57:00.000-05:002009-02-27T12:57:00.000-05:00Why not just call it a Blooming hash table?Why not just call it a Blooming hash table?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-3847517827462633472009-02-27T12:25:00.000-05:002009-02-27T12:25:00.000-05:00A related technique is where you project the datai...A related technique is <BR/>where you project the data<BR/>in a low dimensional space, <BR/>to prune quickly the candidates.<BR/><BR/>An interesting question then... is why stop there? Why not have several filters, progressively more expensive and tighter?<BR/><BR/>I wrote a blog post about this:<BR/><BR/>http://www.daniel-lemire.com/blog/archives/2008/11/20/how-to-speed-up-retrieval-without-any-index/<BR/><BR/><BR/>See also my paper...<BR/><BR/>Daniel Lemire, Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound, to appear in Pattern Recognition.<BR/>http://arxiv.org/abs/0811.3301Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-13579921943828943782009-02-27T12:18:00.000-05:002009-02-27T12:18:00.000-05:00Also, a fairly similar technique is used in databa...Also, a fairly similar technique is used in database hash join implementations when the tables are much larger than disk. You can filter out tuples that won't join and avoid writing them back to disk partitions. Implemented in multiple commercial databases.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-45673327342061497712009-02-27T10:26:00.000-05:002009-02-27T10:26:00.000-05:00How about "Bloom-accelerated hash table"?How about "Bloom-accelerated hash table"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-29043113465003688052009-02-27T09:25:00.000-05:002009-02-27T09:25:00.000-05:00Well, the same technique applies in front of other...Well, the same technique applies in front of other data structures, so more generally it could be "preemptive Bloom Filtering", or "Bloom preFiltering", or even just "using a Bloom Filter"?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-8890204.post-4750508407596286392009-02-27T07:56:00.000-05:002009-02-27T07:56:00.000-05:00I propose we call it a "Mitzenfilter".I propose we call it a "Mitzenfilter".Matt Welshhttps://www.blogger.com/profile/04255792550910131960noreply@blogger.com