Faculty Recruiting Support CICS

Timely Detection of Heavy Hitters in External Memory

01 Oct
Tuesday, 10/01/2019 4:00pm to 5:00pm
Computer Science Building Room 140
Theory Seminar

Given a stream of N elements, an f-heavy hitter is an item that occurs at least fN times in S. The problem of finding heavy-hitters has been extensively studied in the streaming literature. In this talk, the focus will be on a real-time heavy-hitters variant in which an element must be reported shortly after we see its fNth 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).

Like the classic heavy-hitters problem, solving the OEDP without false-positives requires large space (O(N) words), which is not practical in RAM for large streams. In this talk, I will discuss how we adapt heavy-hitters algorithms to external memory to solve the TED problem on large high-speed streams without sacrificingFaculty  accuracy, sensitivity, or timeliness.

Faculty Host