Events Calendar

Speaker

Shikha Singh

Abstract

We consider the problem of timely reporting of heavy hitters in streaming data. Given an input stream of size N, a f-heavy hitter is an item that occurs at least fN times in S. The problem of finding approximate heavy hitters has been extensively studied in the streaming literature. We study a real-time and exact heavy-hitters variant in which an element must be reported shortly after we see its fN-th occurrence (and hence becomes a heavy hitter). We call this the Timely Event Detection (TED) Problem. The TED problem models the needs of many real-world monitoring systems, which demand accurate (i.e., no false negatives) and timely reporting of all events from large, high-speed streams, and with a low reporting threshold (high sensitivity). We show how to adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams while guaranteeing accuracy, sensitivity, and timeliness.

Bio

Shikha Singh is an Assistant Professor of Computer Science at Williams College. She obtained her PhD in Computer Science from Stony Brook University in 2018 and her Integrated MSc. in Mathematics and Computing from Indian Institute of Technology Kharagpur. Shikha's research is in the area of algorithms, with a focus on cache-efficient and adaptive data structures, and algorithmic game theory.