5 ms·

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/spar

by suj1th 9y ago

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?

cmurphycode 9y ago
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 isn't looking good for us!
- loeg 9y ago
  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.)
susam 9y ago
Your parent comment is correct. Consider the use case of space-efficient indexing. A negative response from bloom filter would help the querying engine to skip blocks of data that do not contain the value being searched. If the density of the value is low (i.e., occurs in a small percentage of data blocks), then we can skip a large number of data blocks with the help of bloom filters. But if the density of the value is very high, it implies that the value occurs in most of the data blocks, therefore we would be forced to look at most of the data blocks. In the high density scenario, bloom filters would not provide a significant advantage in reducing the query time, although it would still provide a significant advantage in reducing storage space requirements. See https://news.ycombinator.com/item?id=16435521 https://news.ycombinator.com/item?id=16435521 for an example of such a use case.
loeg 9y ago
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_hash_functions 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 (<10%) is greater than the size of the population, i.e., a bitvector is a smaller representation of the set. (It has other differing properties, too, but size is the one I am focusing on.) Wikipedia shares this observation: https://en.wikipedia.org/wiki/Bloom_filter#Space_and_time_advantages 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.)
deleted 9y ago
[deleted]

by suj1th 9y ago

cmurphycode 9y ago

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 isn't looking good for us!

loeg 9y ago
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.)

susam 9y ago

Your parent comment is correct. Consider the use case of space-efficient indexing. A negative response from bloom filter would help the querying engine to skip blocks of data that do not contain the value being searched. If the density of the value is low (i.e., occurs in a small percentage of data blocks), then we can skip a large number of data blocks with the help of bloom filters. But if the density of the value is very high, it implies that the value occurs in most of the data blocks, therefore we would be forced to look at most of the data blocks. In the high density scenario, bloom filters would not provide a significant advantage in reducing the query time, although it would still provide a significant advantage in reducing storage space requirements. See https://news.ycombinator.com/item?id=16435521 https://news.ycombinator.com/item?id=16435521 for an example of such a use case.

loeg 9y ago

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_hash_functions 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 (<10%) is greater than the size of the population, i.e., a bitvector is a smaller representation of the set. (It has other differing properties, too, but size is the one I am focusing on.) Wikipedia shares this observation: https://en.wikipedia.org/wiki/Bloom_filter#Space_and_time_advantages 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.)

deleted 9y ago

[deleted]