CS Colloquium - Timely Reporting of Heavy Hitters in External Memory

CS Colloquium - Timely Reporting of Heavy Hitters in External Memory promotional image


Shikha Singh


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.


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.

Friday, October 28, 2022 4:00pm to 5:00pm
Seamans Center
103 South Capitol Street, Iowa City, IA 52240
View on Event Calendar
Individuals with disabilities are encouraged to attend all University of Iowa–sponsored events. If you are a person with a disability who requires a reasonable accommodation in order to participate in this program, please contact Computer Science Dept. in advance at 319-335-0713 or matthieu-biger@uiowa.edu.