en.wikipedia.org/wiki/Counting_Bloom_filter
2 corrections found
A counting Bloom filter (CBF) or spectral Bloom filter
"Spectral Bloom filter" is not just another name for a counting Bloom filter. It is a distinct Bloom-filter variant introduced separately for multiset/multiplicity queries.
Full reasoning
The article treats counting Bloom filter and spectral Bloom filter as synonyms, but the literature describes them as related different structures.
- Cohen and Matias's original 2003 paper says the Spectral Bloom Filter (SBF) is "an extension of the original Bloom Filter to multi-sets" and discusses its own multiplicity-query behavior and optimizations.
- Bonomi et al.'s paper on counting Bloom filters discusses spectral Bloom filters in the related-work section as a separate design: "The spectral Bloom filter was designed for multi-sets" and is considered alongside, not as a synonym for, the standard counting Bloom filter.
So a spectral Bloom filter may be based on counting-style counters, but it is not simply another name for a counting Bloom filter.
2 sources
- Spectral Bloom Filters - Tel Aviv University
This paper introduces the Spectral Bloom Filter (SBF), an extension of the original Bloom Filter to multi-sets, allowing the filtering of elements whose multiplicities are below a threshold given at query time.
- An Improved Construction for Counting Bloom Filters
The spectral Bloom filter was designed for multi-sets ... Spectral Bloom filters are primarily designed for multi-sets and skewed streams; we do not know of experiments or other evidence suggesting they are appropriate as a replacement for a CBF.
As a generalized form of the Bloom filter, false positive matches are possible, but false negatives are not
This is too absolute: counting Bloom filters can produce false negatives, especially when deletions are supported and an item is deleted incorrectly.
Full reasoning
This sentence states categorically that counting Bloom filters do not have false negatives. That is not generally correct.
A standard source dedicated to this issue, "False Negative Problem of Counting Bloom Filter", states that counting Bloom filters can in fact return false negatives under standard insertion/query/deletion usage. The paper explains that incorrect deletions—such as deleting an item that only matched because of a false positive—can decrement shared counters and cause later queries for real items to fail.
A separate Bloom-filter survey likewise notes that counting Bloom filters introduce a new error mode: after deletions, false negatives can occur unless one assumes items not in the set are never deleted. So the article's blanket statement is inaccurate unless it is explicitly limited to a no-deletion / well-behaved-operations setting.
2 sources
- False Negative Problem of Counting Bloom Filter
By investigating the mainstream variants, however, we observe that a Bloom filter does return false negatives in many scenarios... the undetectable incorrect deletion of false positive items and detectable incorrect deletion of multiaddress items are two general causes of false negative in a Bloom filter.
- The Bitwise Bloom Filter
Now, false negative error is also possible... if we assume that an element not in the set is never deleted (as is standard practice), then this kind of error is not an issue.