The Online Event-Detection Problem

13/06/2019 - 12:00

Given a stream of N elements, a 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, I will present a related problem. We say that there is a f-event at time t if an element occurs exactly fN times in the stream of elements till time t. Thus, for each f-heavy hitter there is a single f-event which occurs when its count reaches the reporting threshold fN. We define the online event-detection problem (OEDP) as: given f and a stream S, report all f-events as soon as they occur. 

Many real-world monitoring systems demand event detection where all events must be reported (no false negatives), in a timely manner, with no non-events reported (no false positives), and a low reporting threshold. As a result, the OEDP requires a large amount of space (Omega(N) words) and is not solvable in the streaming model or via standard sampling-based approaches. I will focus on cache-efficient algorithms in the external-memory model and present provide algorithms for the OEDP that are within a log factor of optimal.