Jérémie Lumbroso (SFU)
28/02/14 14:30 Talks
Design and Precise Analysis of Some Data Streaming Algorithms
Speaker:
Jérémie Lumbroso (Simon Fraser University)
Abstract:
This talk will present a survey of some data streaming algorithms and focus especially on the distinct element problem: while reading a stream on the fly (and never storing any linear sample of this stream), tell with great accuracy how many distinct elements have appeared in it. For a specific distinct element estimation algorithm based on order statistics, we will show how the analysis of the algorithm can go beyond proving its correctness and giving elementary guarantees, and instead completely characterize the distribution of the algorithm's output using techniques from Analytic Combinatorics and probability analysis.
Date:
Friday, February 28, 2014
Time:
2:30 pm - 3:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Jérémie Lumbroso (Simon Fraser University)
Abstract:
This talk will present a survey of some data streaming algorithms and focus especially on the distinct element problem: while reading a stream on the fly (and never storing any linear sample of this stream), tell with great accuracy how many distinct elements have appeared in it. For a specific distinct element estimation algorithm based on order statistics, we will show how the analysis of the algorithm can go beyond proving its correctness and giving elementary guarantees, and instead completely characterize the distribution of the algorithm's output using techniques from Analytic Combinatorics and probability analysis.
Date:
Friday, February 28, 2014
Time:
2:30 pm - 3:30 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby