Probabilistic data structures - part 1

There are two types of data structures: deterministic and probabilistic.

Deterministic data structures are used to store and retrieve data without losing integrity. They guarantee that when you are running any queries on these data structures, the results will always be accurate. Examples of these data structures include linked lists, hash tables, sets and vectors.

On the other hand, probabilistic data structures do not guarantee accuracy on the query results. They also do not guarantee that you can retrieve the data as it was stored. They are space and time efficient. But queries on them always have a certain error margin. You can usually tune the error margin by adjusting the parameters.

Consider these examples.

  1. You are building a firewall. You want to block a bunch of IP addresses that have misbehaved in the past. When a new request comes, you want to find out if the source IP is one of the blocked IP addresses.

  2. You are running one of the busiest web sites. You are tracking users by user ID cookies. Every day you want to generate a report of how many unique visitors you had for your web site.

  3. You have a global list of malicious URLs. When a user tries to access a web site, you want to check if the URL is a malicious one.

For these examples you can implement a solution using deterministic data structure. For instance, you can use a set. But when there are hundreds of thousands of unique values to be looked up or counted, you will need a lot of memory. That is where probabilistic data strucutres come for help.

In this series, I am going to discuss the following probablistic data structures.

  1. Bloom filter
  2. Counting Bloom filter
  3. Cuckoo filter
  4. Count-min Sketch
  5. HyperLogLog

In this part, we will see Bloom filter.

Bloom filter

Bloom filter is a probabilistic data structure that is efficient to perform membership queries to answer the question "is element present in a set?" When Bloom filter look up returns "false," the element is definitely not present in the set. When the look up returns "true," the element may be present in the set.

Understanding Bloom filter is simple. It works based on two hash functions: h1 and h2. Underlying data structure is a bitmap, say with N bits. Using these two hash functions, you will derive two indices for every element that needs to be inserted or looked up.

When you need to insert an element in the Bloom filter, you do the following:

  def insert(e):
    index1 = h1(e)
    index2 = h2(e)
    set_bit(index1)
    set_bit(index2)

Thats it. To perform look ups, you will compute two indices and check if those two bits are set.

  def is_present(e):
    index1 = h1(e)
    index2 = h2(e)
    return is_bit_set(index1) and is_bit_set(index2)

As more elements are inserted, there is a possibility of look ups returning true even when the element is not present. This is known as false positive. Consider a simple scenario with the following two elements, e1 and e2.

  # h1(e1) -> 10, h2(e1) -> 20
  # h1(e2) -> 30, h2(e2) -> 40

Let us say you are trying to look up an element e3. It may be mapped to two indices as below:

  # h1(e3) -> 20, h2(e3) -> 30
  # This returns true as both bits 20 and 30 are set
  # due to elements e1 and e2.
  is_present(e3) # True

With Bloom filter, it is impossible to reliably remove elements from the set. It is not possible to simply unset the bits corresponding to the indices. Using the same examples above, let us say you have inserted e3 into the Bloom filter. If you unset bits 20 and 30 to remove e3 from filter, look ups on e1 and e2 will start returning false even though they are present.

To overcome this issue, counting Bloom filters can be used.

Field note: I haven't seen Bloom filters used on their own without a backing deterministic data structure. They act as a first line of defense. You perform a look up in Bloom filter. If the answer is false, the answer is returned to the caller immediately. If the answer is true, you usually perform a secondary look up in a deterministic data structure.

References

  • An excellent refence with a simulation is available here

links

social