Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Scalable Bloom Filters (2007) [pdf]

citeseerx.ist.psu.edu

Post reply on HN
Print view View original

31–39 of 39 posts

Re: Scalable Bloom Filters (2007) [pdf]

#31

Post by foo101 »

bhouston wrote: post #2

Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.

> Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.

Perhaps that speaks about the type of work you are involved in rather than about the Hacker News community?

Re: Scalable Bloom Filters (2007) [pdf]

#32

Post by Radim »

3131s wrote: post #30
bhouston wrote: post #2

Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.

I use them for natural language processing. There are cases where the performance increase is enormous (as in I wouldn't be able to afford the computation without them) and the downside of false positives is or can be made irrelevant.

Case in point, collocation detection over very large corpora:

https://github.com/RaRe-Technologies/bounter#example-on-the-...

Reduces RAM requirements some 31x times when automatically detecting common multiword expressions (e.g. "New York", "network license" or "Apache Hadoop"), which is significant.

Re: Scalable Bloom Filters (2007) [pdf]

#34

Post by jxub »

bhouston wrote: post #2

Hacker news loves upvoting articles about bloom filters (and Bayesian probability - its on the front page again this evening.) Personally I've never found a use for either of them in practice.

We use Bloom filters at Datamaran (https://www.datamaran.com) to check if the news site source is in one of the ones we follow quickly.

Re: Scalable Bloom Filters (2007) [pdf]

#35

Post by 3131s »

Radim wrote: post #32
3131s wrote: post #30

Earlier quoted context omitted.

I use them for natural language processing. There are cases where the performance increase is enormous (as in I wouldn't be able to afford the computation without them) and the downside of false positives is or can be made irrelevant.

Case in point, collocation detection over very large corpora: https://github.com/RaRe-Technologies/bounter#example-on-the-... Reduces RAM requirements some 31x times when automatically detecting common multiword expressions (e.g. "New York", "network license" or "Apache Hadoop"), which is significant.

Yep, I load an enormous list of lexemes (including multiword expressions) into a bloom filter and use it for text segmentation.

Re: Scalable Bloom Filters (2007) [pdf]

#36

Post by loeg »

suj1th wrote: post #24
loeg wrote: post #12

Earlier quoted context omitted.

I thought I might have a use for them in practice, but it turns out they are only useful for sparse datasets — if your dataset can be fully populated, a bitmap is more efficient (for any reasonable degree of accuracy).

I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?

You can determine the required size of a bloom filter from population and required error (there are formulas you can find on wikipedia).

See https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of...

> The required number of bits, m, given n (the number of inserted elements) and a desired false positive probability p (and assuming the optimal value of k is used) can be computed by substituting the optimal value of k in the probability expression above: > > This means that for a given false positive probability p, the length of a Bloom filter m is proportionate to the number of elements being filtered n

You will find that the required size (in bits) at any reasonable error (Wikipedia shares this observation:

https://en.wikipedia.org/wiki/Bloom_filter#Space_and_time_ad...

> However, if the number of potential values is small and many of them can be in the set, the Bloom filter is easily surpassed by the deterministic bit array, which requires only one bit for each potential element.

(My use case was tracking allocated blocks in a filesystem, in an application where probabilistic results would have been adequate. It is perfectly valid for 100% of blocks to be allocated, so the required vector size for a bloom filter would be longer than the same-size bitvector.)

Re: Scalable Bloom Filters (2007) [pdf]

#37

Post by loeg »

cmurphycode wrote: post #26
suj1th wrote: post #24

Earlier quoted context omitted.

I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?

Here's a reduced example. I want to ask whether an incoming 16 bit number is in my set. I can make a bitmap that answers that question perfectly in 8KB :) So I'm assuming what the parent meant by sparse is, things where the universe is much much bigger, and therefore the things in your set are a sparse proportion of the universe. For instance, in deduplication, we use at least 160 bit hash functions...and that bitmap…

The other half of it is, your hypothetical set contains over 2^15 individual entries (i.e., it's not sparsely populated).

(My use case was tracking allocated blocks in a filesystem, in an application where probabilistic results would have been adequate. It is perfectly valid for 100% of blocks to be allocated, so the required vector size for a bloom filter would be longer than the same-size bitvector.)

Re: Scalable Bloom Filters (2007) [pdf]

#38

Post by [deleted] »

suj1th wrote: post #24
loeg wrote: post #12

Earlier quoted context omitted.

I thought I might have a use for them in practice, but it turns out they are only useful for sparse datasets — if your dataset can be fully populated, a bitmap is more efficient (for any reasonable degree of accuracy).

I don't see how this is true. The bitmap vs bloom-filters argument is more about accuracy (BFs have a one-way error, Bitmaps do not). The datasets' density/sparsity has no bearing on efficiency, AFAIK. Would you elaborate your reasoning?

[deleted]

Re: Scalable Bloom Filters (2007) [pdf]

#39

Post by opencoff »

I used this paper for building a scalable bloom filter for use in an ad-tech stack. The performance was better than DJB's CDB.

https://github.com/opencoff/portable-lib

The bloom filter code is in src/bloom.c; the Header file is in inc/utils/bloom.h

I implemented a serialization/deserialization of the bloom filters as well (src/bloom_marshal.c).

The tests are in test/t_bloom.c.

Post reply on HN