Past Meetup

Data Streams as Random Permutations: the Distinct Element Problem

This Meetup is past

27 people went

Verse HQ

Plaça Catalunya 21, 3rd floor · Barcelona

How to find us

It's the same building as Hard Rock Cafe in the Plaza Catalunya. Entrance from the side of the building. 3rd floor, Verse HQ office.

Location image of event venue

Details

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.