Space efficiency

There have been 1 completed talk tagged with space efficiency.

Related Tags

• bloom filter
• data structure
• algorithm
• probability
• computer science

Completed Talks

Bloom Filters and Other Probabilistic Data Structures

Delivered by Luthfi Mawarid on Friday March 3, 2017

With the advent of big data, the ability to process large volumes of data is becoming increasingly important. For instance, when dealing with large data sets, we may want to perform simple operations such as counting the number of unique elements or checking whether or not an element is present in the set. While there are deterministic data structures, such as hash tables, that can perform these quickly, the sheer size of the data involved makes their use largely impractical and unscalable.Instead, we may want to trade-off some accuracy in our answers in exchange for greater space efficiency and ease of parallelization. For this, we introduce the concept of probabilistic data structures.

In this talk, we will mainly focus on Bloom filters, which are commonly used to test set membership and speed up data access. We will explore its main use cases, its implementation details, and the mathematics behind it. If time permits, I will also talk about the count min-sketch, used for frequency counting, and/or the HyperLogLog counter, used for cardinality estimation.

This talk will assume basic knowledge of probability.