The Bloom filter

Back


Google Tech Talks
November, 15 2007

ABSTRACT

The Bloom filter, conceived by Burton H. Bloom in 1970, is a
space-efficient probabilistic data structure that is used to test
whether an element is a member of a set. False positives are possible,
but false negatives are not. Elements can be added to the set, but not
removed (though this can be addressed with a counting filter). The
more elements that are added to the set, the larger the probability of
false positives.

For example, one might use a Bloom filter to do spell-checking in a
space-efficient way. A Bloom filter to which a dictionary of correct
words has been added will accept all words in the dictionary and
reject almost all words which are not, which is good enough in some
cases. Depending on the false positive rate, the resulting data
structure can require as little as a byte per dictionary word.

In the last few years Bloom filter become hot topic again and there
were several modifications and improvements. In this talk I will
present my last few improvements in this topic.


Speaker: Ely Porat
Ely Porat received his Doctorate from Bar-Ilan University in 2000.
Following that, he fulfilled his military service and, in parallel,
worked as a faculty member at Bar-Ilan University. Having spent the
spring 2007 semester as a Visiting Scientist in Google, he is now back
at Bar-Ilan University.

The main body of Ely Porat's work concerns matching problems: string
matching, pattern matching, subset matching. He also worked on the
nearest pair problem in high-dimensional spaces as well as sketching
and edit distance.

Channel: People & Blogs
Uploaded: April 12, 2008 at 12:06 pm
Author: googletechtalks

Length: 00:47:40
Rating: 3.89
Views: 8753

Tags: google techtalks techtalk engedu talk talks googletechtalks education

Video Comments:
rationalpsychedelia (September 19, 2008 at 6:42 am)
yea, i cant understand this guy and Im not a native speaker myself
LKTI (July 10, 2008 at 8:25 pm)
Nice or erotic .The Luxury Woman Of the Millenium....One of a kind outfits and personality!!! Cuz i am hot and willing to fulfill your wishes. After all life is short, we have to make it good and pick as much fun as we can. come visit me at FriendlyFlirts * COM my user-id there is Alyssa-mkel chat soon on cam :) ffwyswxij
NNNUTZ (July 9, 2008 at 4:55 pm)
I hope i'll make a lot of new friends here , i'd like to show my great body for you, i'd like to give you the greatest pleasure you've ever had..mmmmmmmm..Im getting hot just thinking about it come visit me at FriendlyFlirts * COM my user-id there is Ashley-pcwn chat soon on cam :) motljtdwlv
jvangael (April 19, 2008 at 10:14 pm)
ok talk: speaker doesn't master english very well which makes it a bit annoying to listen.
REALGREYBLUE (April 14, 2008 at 3:05 am)
Can you hear me now? :)
REALGREYBLUE (April 14, 2008 at 2:55 am)
This is one step closer to perfection. False positives ....collect the whole set. :) I've been Googleized.