Abstract

Given a stream S=(s1,s2,...,sN), a ϕ-heavy hitter is an item si that occurs at least ϕN times in S. The problem of finding heavy-hitters has been extensively studied in the database literature. In this paper, we study a related problem. We say that there is a ϕ-event at time t if st occurs exactly ϕN times in (s1,s2,...,st). Thus, for each ϕ-heavy hitter there is a single ϕ-event which occurs when its count reaches the reporting threshold ϕN. We define the online event-detection problem (OEDP) as: given ϕ and a stream S, report all ϕ-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 (Ω(N) words) and is not solvable in the streaming model or via standard sampling-based approaches. Since OEDP requires large space, we focus on cache-efficient algorithms in the external-memory model.

We provide algorithms for the OEDP that are within a log factor of optimal. Our algorithms are tunable: its parameters can be set to allow for a bounded false-positives and a bounded delay in reporting. None of our relaxations allow false negatives since reporting all events is a strict requirement of our applications. Finally, we show improved results when the count of items in the input stream follows a power-law distribution.

Details

Prashant Pandey and Shikha Singh are equal first authors on this paper.

Date

June, 2020

Authors

  • Prashant Pandey
  • Shikha Singh
  • Michael A. Bender
  • Jonathan W. Berry
  • Martin Farach-Colton
  • Rob Johnson
  • Thomas M. Kroeger
  • Cynthia A. Phillips

Related projects

Research Areas

  • External-Memory Algorithms
  • External-Memory Data Structures
  • Streaming Algorithms

Type

Inproceedings

Booktitle

SIGMOD