Hi Jeffrey, On Mon, Jun 8, 2009 at 2:00 PM, Jeffrey Bosboom<jbosboom@uci.edu> wrote:
Dean Michael Berris wrote:
During the weekend, I got acquainted with and excited about Bloom Filters and the utility of such a data structure.
I've only heard of bloom effects as used in 3D graphics for more realistic lighting effects. Looking at the code, that does not seem to be the purpose of your bloom filter. Just what is it and why might I use it?
A Bloom Filter is a space efficient data-structure that allows you to represent set membership that allows for false positives (elements may have been marked as included in a set when they really aren't part of the set) but not false negatives (when an element has not been included/added in the set, the bloom filter wouldn't show that they are part of the set). These have been used in proxy caches to signify whether they already have a cached copy of a URI. File systems also use these to see whether a part of a file (or a page) has already been accessed before (to limit the frequency of fetching pages that have been fetched before on a DFS for instance). A more in-depth explanation of bloom filters can be found here: http://en.wikipedia.org/wiki/Bloom_filter HTH -- Dean Michael Berris | Software Engineer, Friendster, Inc. blog.cplusplus-soup.com | twitter.com/mikhailberis | linkedin.com/in/mikhailberis | profiles.friendster.com/mikhailberis | deanberris.com