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?
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!
(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.)
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 (<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_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.)
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 for an example of such a use case.