Campus Event Calendar
Event Entry
What and Who
Online Sampling with Minimal Randomness
Davis Issac
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 25 August 2015
13:00
30 Minutes
E1 4
024
Saarbrücken
Abstract
We study the amount of randomness required to sample an item from a stream of items. The items keep on arriving and we need to store a single element from the items seen so far. The sampled element at any point of time should be an uniform sample of the elements seen so far. We give an algorithm which does this using $O(\log n)$ random bits. This matches the offline lower bound for the problem. Our algorithm is also space and time efficient.
Contact
Davis Issac
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
discrete sampling; streaming algorithms
Davis Issac, 08/10/2015 15:23
Davis Issac, 08/10/2015 15:22 -- Created document.
Davis Issac, 08/10/2015 15:22 -- Created document.