Probability

Bloom Filters

Shreya Jayaraman and Luxi Wang

Alex Tsun

​

Agenda

• Deterministic Data Structures
• Probabilistic Data Structures
• Bloom Filters

Data Structures

Data Structures

• Handle data organization, management, and storage
• Collection of data, relationships between data, and operations that manipulate the data

Deterministic Data Structures

• The ones you’re likely familiar with
• Starting with an empty data structure and applying a series of operations (insert, delete, etc.) gives the same resulting structure

4

6

2

1

3

5

7

arrays/lists

maps/dictionaries

trees

Probabilistic Data Structures

• Data structures that rely on a random number generator, or have some aspect of their output probabilistic
• This makes their output after a series of operations unpredictable

Probabilistic Data Structures

• Data structures that rely on a random number generator, or have some aspect of their output probabilistic
• This makes their output after a series of operations unpredictable
• Why use them?
• Reduce time complexity (in expectation)
• Reduce space complexity (in expectation)
• Reduce “code complexity” (meaning “easier to understand” or “easier to code up”)

Random Picture

Definition of

Expectation

Hashing and Probabilities

Bloom Filters

• Probabilistic implementation of sets (unordered collection of unique objects)
• Rely on hashing

Bloom Filters

• Probabilistic implementation of sets (unordered collection of unique objects)
• Rely on hashing

​

Hashing (Motivation):

If we want to store elements in some

structure like a list/array, checking

whether an element is in it requires

searching the entire array. Can we do

better?

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.

​

​

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

​

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

​

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

​

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

• To insert or find a string, just use h to determine its location!

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

• To insert or find a string, just use h to determine its location!
• Want to have minimal collisions (multiple strings hashing to same location.

​

​

​

Hashing

• We want to store the strings “hello” and “bye” in a structure, and have quick insert AND lookup times.
• Suppose we have a “magical” function h that maps strings to indices (integers). e.g. h(“bye”) = 3, h(“hello”) = 0

​

​

• To insert or find a string, just use h to determine its location!
• Want to have minimal collisions (multiple strings hashing to same location.
• Have our hash function h behave “uniformly at random”, but consistent.

​

​

Bloom Filters

Bloom Filters: Motivation

• Google Chrome has a database of malicious URLs, but it takes a long time to query.

​

​

Bloom Filters: Motivation

​

• Google Chrome has a database of malicious URLs, but it takes a long time to query.
• Want an in-browser structure, so needs to be efficient and be space-efficient

​

​

Bloom Filters: Motivation

​

• Google Chrome has a database of malicious URLs, but it takes a long time to query.
• Want an in-browser structure, so needs to be efficient and be space-efficient
• Want it so that can check if a URL is in structure:
• If return False, then definitely not in the structure (don’t need to do expensive database lookup, website is safe)

​

​

Bloom Filters: Motivation

​

• Google Chrome has a database of malicious URLs, but it takes a long time to query.
• Want an in-browser structure, so needs to be efficient and be space-efficient
• Want it so that can check if a URL is in structure:
• If return False, then definitely not in the structure (don’t need to do expensive database lookup, website is safe)
• If return True, the URL may or may not be in the structure. Have to perform expensive lookup in this rare case.

​

​

Bloom Filters

• Supports two key operations:
• add(x) - adds x to bloom filter
• contains(x) - returns true if x in bloom filter, otherwise returns false
1. If return false, definitely not in structure.
2. If return true, possibly in the structure (some false positives).

​

​

Bloom Filters

• Supports two key operations:
• add(x) - adds x to bloom filter
• contains(x) - returns true if x in bloom filter, otherwise returns false
• If return false, definitely not in structure.
• If return true, possibly in the structure (some false positives).

​

• Does not support the following operations:
• removing an element from bloom filter
• giving a collection of elements in the structure

Bloom Filters

• Why accept false positives?
• Speed - add and contains have good time complexity
• Space - doesn’t require much space relative to items to be stored

Bloom Filters

Hash Tables

• These store the data itself
• Therefore, they need at least as much space as all the data being stored
• E.g. in the case of malicious URLS, store strings

Bloom Filters

• These don’t store the data itself
• They only store bit arrays - 0/1s - bits are very small and use much less space

Bloom Filters: Initialization

Size of bloom filter

Number of hash functions

for each hash function, initialize an empty bit vector of size m

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

Bloom Filters: Add

for each hash function h_i

h_i(x) → result of hash function h_i on x

Bloom Filters: Add

for each hash function h_i

Index into ith bit-vector, at index produced by hash function and set to 1

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“thisisavirus.com”)

h₁(“thisisavirus.com”) → 2

h₂(“thisisavirus.com”) → 1

h₃(“thisisavirus.com”) → 4

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“thisisavirus.com”)

h₁(“thisisavirus.com”) → 2

h₂(“thisisavirus.com”) → 1

h₃(“thisisavirus.com”) → 4

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“thisisavirus.com”)

h₂(“thisisavirus.com”) → 1

h₃(“thisisavirus.com”) → 4

h₁(“thisisavirus.com”) → 2

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“thisisavirus.com”)

h₁(“thisisavirus.com”) → 2

h₃(“thisisavirus.com”) → 4

h₂(“thisisavirus.com”) → 1

Bloom Filters: Contains

Returns True if the bit vector for each hash function has bit 1 at index determined by that hash function, otherwise returns False

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

contains(“thisisavirus.com”)

h₁(“thisisavirus.com”) → 2

h₂(“thisisavirus.com”) → 1

h₃(“thisisavirus.com”) → 4

True

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

contains(“thisisavirus.com”)

h₂(“thisisavirus.com”) → 1

h₃(“thisisavirus.com”) → 4

True

True

h₁(“thisisavirus.com”) → 2

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

contains(“thisisavirus.com”)

h₃(“thisisavirus.com”) → 4

True

True

True

h₂(“thisisavirus.com”) → 1

h₁(“thisisavirus.com”) → 2

Bloom Filters: Example

bloom filter t of length m = 5 that uses k = 3 hash functions

contains(“thisisavirus.com”)

h₃(“thisisavirus.com”) → 4

True

True

True

Since all conditions satisfied, returns True (correctly)

h₂(“thisisavirus.com”) → 1

h₁(“thisisavirus.com”) → 2

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“totallynotsuspicious.com”)

h₁(“totallynotsuspicious.com”) → 1

h₂(“totallynotsuspicious.com”) → 0

h₃(“totallynotsuspicious.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“totallynotsuspicious.com”)

h₁(“totallynotsuspicious.com”) → 1

h₂(“totallynotsuspicious.com”) → 0

h₃(“totallynotsuspicious.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“totallynotsuspicious.com”)

h₁(“totallynotsuspicious.com”) → 1

h₂(“totallynotsuspicious.com”) → 0

h₃(“totallynotsuspicious.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“totallynotsuspicious.com”)

h₁(“totallynotsuspicious.com”) → 1

h₂(“totallynotsuspicious.com”) → 0

h₃(“totallynotsuspicious.com”) → 4

Collision, is already set to 1

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

add(“totallynotsuspicious.com”)

h₁(“totallynotsuspicious.com”) → 1

h₂(“totallynotsuspicious.com”) → 0

h₃(“totallynotsuspicious.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

contains(“verynormalsite.com”)

h₁(“verynormalsite.com”) → 2

h₂(“verynormalsite.com”) → 0

h₃(“verynormalsite.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

True

contains(“verynormalsite.com”)

h₁(“verynormalsite.com”) → 2

h₂(“verynormalsite.com”) → 0

h₃(“verynormalsite.com”) → 4

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

True

True

contains(“verynormalsite.com”)

h₂(“verynormalsite.com”) → 0

h₃(“verynormalsite.com”) → 4

h₁(“verynormalsite.com”) → 2

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

True

True

True

contains(“verynormalsite.com”)

h₃(“verynormalsite.com”) → 4

h₂(“verynormalsite.com”) → 0

h₁(“verynormalsite.com”) → 2

Bloom Filters: False Positives

bloom filter t of length m = 5 that uses k = 3 hash functions

True

True

True

Since all conditions satisfied, returns True (incorrectly)

contains(“verynormalsite.com”)

h₃(“verynormalsite.com”) → 4

Bloom Filters

h₂(“verynormalsite.com”) → 0

h₁(“verynormalsite.com”) → 2

Bloom Filters: Summary

• An empty bloom filter is an empty k x m bit matrix with all values initialized to zeros
• k = number of hash functions
• m = size of bloom filter
• add(x) runs in O(k) time
• contains(x) runs in O(k) time
• requires O(km) space
• Probability of false positives from collisions can be reduced by increasing the size of the bloom filter

END PIC

​

Alex Tsun