2 ms·
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
by 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.