13 BLOOM FILTERS

Question 1

What is a Bloom filter?

Answer 1

A data structure that optimizes memory usage and execution time to track keys and answer if a key has been seen before.

Question 2

Who invented Bloom filters and when?

Answer 2

Burton Bloom in 1970.

Question 3

What simple question does a Bloom filter answer?

Answer 3

Have we previously seen this key?

Question 4

What is the main drawback of Bloom filters?

Answer 4

They can produce false positives.

Question 5

What is guaranteed about Bloom filters regarding false negatives?

Answer 5

They guarantee a lack of false negatives.

Question 6

How does a Bloom filter improve search efficiency?

Answer 6

By first checking the Bloom filter before accessing a larger data structure.

Question 7

What happens when a Bloom filter returns false?

Answer 7

The record is not in the data set, and the expensive lookup can be skipped.

Question 8

What type of data structure is a Bloom filter fundamentally?

Answer 8

An array of binary values.

Question 9

In a Bloom filter, what does a value of 1 indicate?

Answer 9

That a given bin has been seen before.

Question 10

What is the primary purpose of the Bloom filter?

Answer 10

To filter over a large key space with low memory overhead.

Question 11

How does a Bloom filter handle collisions?

Answer 11

By using multiple independent hash functions.

Question 12

What is the result of using k independent hash functions in a Bloom filter?

Answer 12

It reduces the likelihood of false positives.

Question 13

Fill in the blank: A Bloom filter uses _______ to map keys to indices.

Answer 13

k independent hash functions.

Question 14

True or False: A Bloom filter can guarantee that a key is in the data set if it returns true.

Answer 14

False.

Question 15

What is the relationship between the size of the Bloom filter and the number of hash functions?

Answer 15

Balancing them can reduce the probability of false positives.

Question 16

What analogy is used to explain how a Bloom filter works?

Answer 16

Asking a knowledgeable event organizer about a friend in a crowded ballroom.

Question 17

What is a significant advantage of using a Bloom filter in searching?

Answer 17

It can avoid many pointless searches.

Question 18

What happens when too many values are inserted into a simple binary indicator array?

Answer 18

It leads to hash collisions and false positives.

Question 19

How does a Bloom filter determine if a key exists?

Answer 19

All k array values must be 1 for the key to be considered present.

Question 20

What is an example application of a Bloom filter mentioned in the text?

Answer 20

Checking if a password is on a list of known weak passwords.

Question 21

In the context of Bloom filters, what does a false positive mean?

Answer 21

Indicating that a key has been inserted when it has not.

Question 22

What is one method suggested to improve a simple single-hash-function filter?

Answer 22

Increase the size of the binary array.

Question 23

What concept does the Bloom filter utilize to optimize searching through large data sets?

Answer 23

A two-stage lookup process.

Question 24

What is a Bloom filter used for in the context of trying new coffee?

Answer 24

To quickly determine if a new coffee should be sampled based on five attributes.

Question 25

What attributes are used to construct a Bloom filter for coffees?

Answer 25

Primary smell and viscosity, among others.

Question 26

What happens if any attribute maps to 0 in a Bloom filter?

Answer 26

The new coffee can be safely consumed, as it is guaranteed not to be on the barista's list.

Question 27

What is the structure of a Bloom filter in code?

Answer 27

BloomFilter { Integer: size, Integer: k, Array of bits: bins, Array of hash functions: h }

Question 28

What are the functions used to manipulate a Bloom filter?

Answer 28

BloomFilterInsertKey and BloomFilterLookup.

Question 29

True or False: The runtime of both insertion and lookup in a Bloom filter is dependent on the number of items inserted.

Answer 29

False.

Question 30

What factors impact the false positive rate of a Bloom filter?

Answer 30

* Size of the array (m) * Number of hash functions (k) * Number of items inserted (n)

Question 31

What is the formula for approximating the false positive rate of a Bloom filter?

Answer 31

FalsePositiveRate = (1 – (1 – 1/m)^(nk))^k

Question 32

What happens to the false positive rate when the size of the array is increased?

Answer 32

It decreases.

Question 33

What is the consequence of increasing the number of items inserted into a Bloom filter?

Answer 33

It increases the false positive rate.

Question 34

How does the number of hash functions (k) affect the false positive rate?

Answer 34

It can increase or decrease the rate depending on other parameters.

Question 35

What is the tradeoff when tuning Bloom filter parameters?

Answer 35

Between false positive rate, computational cost, and memory cost.

Question 36

What is a significant advantage of Bloom filters over hash tables?

Answer 36

Bloom filters use significantly less memory.

Question 37

Why might hash tables be less efficient than Bloom filters in terms of memory?

Answer 37

Hash tables require storing keys and pointers, leading to more memory usage.

Question 38

How can Bloom filters optimize computationally sensitive applications?

Answer 38

By keeping the filter in memory or cache for fast access.

Question 39

What is the key characteristic of the accuracy of a Bloom filter's lookup operation?

Answer 39

It is probabilistic and can return false positives.

Question 40

What does the next chapter focus on after discussing Bloom filters?

Answer 40

Data structures that use randomness to avoid bad worst-case behavior, such as skip lists.