Date Added: Jan 2011
High-speed monitoring of Internet traffic is an important and challenging problem, with applications to real time attack detection and mitigation, traffic engineering, etc. However, packet-level monitoring requires fast streaming algorithms that use very little memory and little communication among collaborating network monitoring points. In this paper, the authors consider the problem of detecting superspreaders, which are sources that connect to a large number of distinct destinations. They propose new streaming algorithms for detecting superspreaders and prove guarantees on their accuracy and memory requirements.