Abstract
We consider the quantitative group testing problem where the objective is to identify defective items in a given population based on results of tests performed on subsets of the population. Under the quantitative group testing model, the result of each test reveals the number of defective items in the tested group. The minimum number of tests achievable by nested test plans was established by Aigner and Schughart in 1985 within a minimax framework. The optimal nested test plan offering this performance, however, was not obtained. In this work, we establish the optimal nested test plan in closed form. This optimal nested test plan is also asymptotically (as the population size grows to infinity) optimal among all test plans. We then focus on the application of heavy hitter detection problem for traffic monitoring and anomaly detection in the Internet and other 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. Since the volume of heavy hitters is much higher than that of normal flows, the number of heavy hitters in a group of flows can be accurately estimated from the aggregated traffic load. Other potential applications include detecting idle channels in the radio spectrum in the high SNR regime.
Introduction
Identifying "heavy hitters"—rare, high-volume data flows that dominate network bandwidth—is a critical task for traffic monitoring and anomaly detection. In massive populations of millions of flows, individual inspection is computationally prohibitive at line speeds. Group testing offers a more efficient alternative by pooling items and testing them collectively. While traditional group testing provides binary (yes/no) results, quantitative group testing reveals the exact number of defective items (heavy hitters) within a group, significantly increasing the information gain per test.
This paper provides the first closed-form solution for the optimal "nested" test plan in quantitative group testing. By solving a long-standing open problem from 1985, the authors establish a plan that is not only mathematically elegant but also asymptotically optimal as population size grows.
The Optimal Nested Test Plan
The core theoretical contribution is the derivation of explicit formulas for the total number of tests $N(n,d)$ and the size of the first group test $M(n,d)$ for a population $n$ with $d$ heavy hitters. The authors utilize a minimax framework to minimize the worst-case number of tests.
The Frame and Segment Structure
The optimal test plan follows a distinct "frame and segment" pattern. The population is partitioned into frames of exponentially increasing length ($2^l$), which are further subdivided into $d$ segments. Within each segment, the number of tests remains constant, while the optimal size for the first group test grows linearly.
This structure allows for the identification of all $d$ heavy hitters in $O(d \log(n/d))$ tests. This logarithmic efficiency ensures that the method remains scalable even as network traffic volumes explode.
Performance and Practical Application
To bridge theory and practice, the authors apply their test plan to synthetic network traffic modeled by Poisson and Log-normal distributions. Since real-world traffic volume isn't a perfect integer, Maximum Likelihood (ML) and sample mean estimators are used to "count" heavy hitters in aggregated samples based on these probabilistic models.
Efficiency and Accuracy
Simulations demonstrate that the plan maintains high accuracy with very low false-positive and false-negative rates. The efficiency of the plan is visualized in the step-like growth of the number of tests required as the population size increases.
The success of the method is closely tied to the "Signal-to-Noise Ratio." As the fraction of total traffic volume contributed by heavy hitters increases, detection error rates drop toward zero. Furthermore, if the total number of heavy hitters $d$ is initially unknown, the authors prove that the mathematically optimal first step is to test the entire population to determine $d$ before proceeding with the nested plan.
Conclusion
This work transitions quantitative group testing from a theoretical curiosity to a practical tool for network engineering. By providing the first closed-form optimal nested test plan, the authors offer a blueprint for efficient traffic monitoring. Future work will need to address the challenges of dynamic flow environments and the hardware constraints of real-time implementation in programmable data planes like P4.
Summary updated