Data Streams as Random Permutations: the Distinct Element Problem

Data Streams as Random Permutations (Paper) (https://hal.inria.fr/hal-01197221/document)

Presented by Jordi Montes, Research Engineer

Abstract:

Cardinality estimation has a wide range of applications from databases to network systems. The problem has been studied since the 80's and many algorithms have been proposed: Adaptive Sampling, HyperLogLog or Recorinality to say some of them.

In this talk we will discuss why cardinality estimation is an important problem, how it has been solved before and why looking at data streams as random permutations can be useful (Hint: This simple observation allows a wealth of classical and recent results from combinatorics to be recycled, with minimal effort, as estimators for various statistics over data streams.).

Talk will be based on this paper ( https://hal.inria.fr/hal-01197221/document ) but audience is not expected to know the paper or have previous exposure to this topic.