Paper Info
Title
Group testing under sum observations for heavy hitter detection
Abstract
We introduce a variation of the classic group testing problem referred to as group testing under sum observations. In this new formulation, when a test is carried out on a group of items, the result reveals not only whether the group is contaminated, but also the number of defective items in the tested group. We establish the optimal nested test plan within a minimax framework that minimizes the total number of tests for identifying all defective items in a given population. This optimal test plan and its performance are given in closed forms. It guarantees to identify all d defective items in a population of n items in O(d log <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> (n/d)) tests. This new formulation is motivated by the heavy hitter detection problem in traffic monitoring in Internet and general communication networks. For such applications, it is often the case that a few abnormal traffic flows with exceptionally high volume (referred to as heavy hitters) make up most of the traffic seen by the entire network. To detect the heavy hitters, it is more efficient to group subsets of flows together and measure the aggregated traffic rather than testing each flow one by one. Since the volume of heavy hitters is much higher than that of normal flows, the number of heavy hitters in a group can be accurately estimated from the aggregated traffic load. The problem also finds applications in detecting idle channels in the spectrum in the high SNR regime.
Year
DOI
Venue
2014
10.1109/ITA.2015.7308980
2015 Information Theory and Applications Workshop (ITA)
Keywords
DocType
Volume
Group testing,heavy hitter detection,anomaly detection,traffic measurements
Journal
abs/1407.2283
Citations 
PageRank 
References 
3
0.43
8
Authors
3
Name
Order
Citations
PageRank
Chao Wang151.59
Qing Zhao277258.53
Chen-Nee Chuah32006161.34