In: Computer Science
Select all that hold true about Bloom Filters:
Select one or more:
A. Bloom Filter has a predictable false positive rate. (Incorrect choices are penalized)
B. The total storage required for a Bloom Filter is fixed to be mm bits, and this won't increase regardless of the number of values stored.
C. Each search operation can be processed in the order
of O(n×k)O(n×k) by a Bloom Filter with kk hash functions
that already added nn values.
D. Each search or insert operation only requires O(k)O(k) operations by a Bloom Filter with kk hash functions and the cost does not depend on either the number of bits used by the Bloom Filter or nn, the number of values already added.
E. While the size of the bit array used by the Bloom Filter is constant, it may need to be quite large to reduce the false positive rate.
F. The Bloom Filter supports the following operations: add/insert the element, search the element, and remove the element.
G. While risking false positives, Bloom Filters have a strong space advantage over other data structures for representing sets, such as self-balancing binary search trees, tries, has tables, simple arrays or linked lists.
H. The Bloom Filter also stores the data items themselves that could be retrieved in O(k)O(k) time
Answer)
The following are the valid statements regarding the Bloom filters
:
A. A bloom filter has a predictable false positive rate.
B. The total storage required for a bloom filter is fixed to be m
bits and this won't increase regardless of the number of values
stored
D. Each search or insert operation only requires O(k)O(k)
operations by a Bloom Filter with kk hash functions and the cost
does not depend on either the number of bits used by the Bloom
Filter or nn, the number of values already added.
E. While the size of the bit array used by the Bloom Filter is
constant, it may need to be quite large to reduce the
false-positive rate.
G.
The bloom filters have a false positive rate, reducing the size of
the bit array used reduces the false positive rate. Bloom filters
will be having better space advantage.
**Please Hit Like if you appreciate my answer. For further doubts on the or answer please drop a comment, I'll be happy to help. Thanks for posting.**