Reference no: EM133958057

Assignment:

Probabilistic Data Structures

a) This question is about exploring an important data structures from internet and writing 3-4 paragraphs about it for learning purposes. Specifically, what is a Bloom Filter? Describe algorithmically how it works, you can give some basic examples to demonstrate how it works. What kind of space and false positive trade-off a Bloom Filter offers? Please do not copy-paste from internet, explain it with your own words  and cite your resources.

b) Let's assume a bloom filter it has m-bit length and uses k hash ideal functions. Also assume we will enter n elements in it consecutively. What is the false positive probability expressed in terms of (m,k,n) variables? Explain how you compute it step by step by step. As a hint, one can explain in 4-5 simple steps (some steps you can combine some steps).

c) What is a Cuckoo Filter? Explain how it works, and elaborate its advantages and disadvantages with respect to Bloom Filter. The ideal answers could be 3-4 paragraph, and give algorithmic and mathematical explanations, story-like descriptions will not be considered!