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 order optimal among all test plans as the population size approaches infinity. Using heavy-hitter detection as a case study, we show via simulation examples orders of magnitude improvement of the group testing approach over two prevailing sampling-based approaches in detection accuracy and counter consumption.
Introduction
Group testing (GT) was originally designed to efficiently identify rare "defective" items (like infected blood samples) by testing pools of items together. In Classic GT, a test is binary: it indicates if at least one defective item is present. In Quantitative GT (QGT), a test is more informative, revealing the exact number of defectives in the pool. This is often referred to as the "coin weighing problem."
While the theoretical minimum number of tests for a specific class of "nested" adaptive plans (where each test is a subset of the previous one) was established in 1985, the actual optimal plan—the specific instructions on how large each test group should be—remained an open problem for over 30 years. This paper provides the first closed-form optimal nested test plan for QGT and demonstrates its practical utility in network heavy-hitter detection, where current sampling methods struggle under strict hardware memory constraints.
Methods: The Optimal Nested Strategy
The authors focus on Combinatorial Quantitative Group Testing (CGT), a minimax formulation that aims to minimize the number of tests in the worst-case scenario. They derive a compact, closed-form expression for $N(n, d)$ (the minimum number of tests for $n$ items and $d$ defectives) and $M(n, d)$ (the optimal size of the first group to test).
The strategy utilizes a tree-structured adaptive plan. If a test reveals $d_1$ defectives in a group, the problem recursively splits into two smaller, independent sub-problems. This recursive approach is formalized in the NESTED algorithm.
Key Insights and Structural Optimality
A core contribution of this work is revealing that the optimal test sequence follows a geometric "frame-segment" structure. The population is partitioned into frames that double in length, and each frame is subdivided into $d$ segments. This geometric scaling ensures that the proposed nested plan is "order optimal," meaning as the population size $n$ goes to infinity, the number of tests scales at the same rate as the theoretical information-theoretic lower bound.
Furthermore, the authors prove that if the total number of defectives $d$ is unknown, the optimal first step is always to test the entire population. This immediately reveals $d$ and reduces the problem to a known-$d$ scenario, demonstrating the inherent power of quantitative outcomes over binary ones.
Performance in Heavy-Hitter Detection
The researchers applied this framework to network traffic monitoring, treating "heavy hitters" (high-volume flows) as defectives. By "weighing" the total packet count of flow aggregates, they can estimate the number of heavy hitters using Maximum Likelihood Estimation (MLE).
In simulations with 1,000 flows, the QGT approach achieved false positive and negative rates near $10^{-3}$ with a very small observation window. In contrast, standard sampling-based methods like Sampled NetFlow remained stuck at much higher error rates ($10^{-1}$ to $10^{-2}$).
As shown in the performance comparison, the optimal nested plan significantly outperforms traditional binary splitting methods. For the same level of detection accuracy, QGT reduced counter consumption (TCAM entries in a router) from hundreds to only a handful, maintaining robustness even under heavy-tailed (log-normal) traffic distributions.
Conclusion
By providing the first explicit construction of the optimal nested test plan for QGT, this work bridges a significant gap in information theory. The demonstrated orders-of-magnitude improvement in resource efficiency and accuracy for heavy-hitter detection suggests broad applicability in anomaly detection and wideband spectrum sensing for cognitive radio systems. Future research may extend this to semi-quantitative models where test results are provided as intervals rather than exact counts.
Summary updated