Computer Science Department
School of Computer Science, Carnegie Mellon University
New Streaming Algorithms for Fast Detection
Shobha Venkataraman, Dawn Song,
In this paper, we consider the problem of detecting superspreaders, which are sources that connect to a large number of distinct destinations. We propose several new streaming algorithms for detecting superspreaders, and prove guarantees on their accuracy and memory requirements. We also show experimental results on real network traces. Our algorithms are substantially more efficient (both theoretically and experimentally) than previous approaches. We also provide several extensions to our algorithms -- we show how to identify superspreaders in a distributed setting, with sliding windows, and when deletions are allowed in the stream.
More generally, our algorithms are applicable to any problem that can be formulated as follows: given a stream of (x,y) pairs, find all the x's that are paired with a large number of distinct y's. We call this the heavy distinct-hitters problem. There are many network security applications of this general problem. This paper discusses these and other applications, and for concreteness, focuses on the superspreader problem.
*Intel Research Pittsburgh