Optimal Nested Test Plan for Combinatorial Quantitative Group Testing

Chao Wang, Qing Zhao, Chen-Nee Chuah

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 is a classical combinatorial problem aimed at identifying a small number of "defective" items within a large population by testing groups rather than individuals. In Quantitative Group Testing (QGT), a test result reveals the exact number of defective items in the group, rather than a simple binary indicator.

While the theoretical minimum number of tests for "nested" strategies—where each subsequent test is a subset of a previous group found to contain defectives—has been known since 1985, the specific sequence of group sizes to achieve this minimum remained an open problem. This paper provides the first closed-form solution for the optimal nested test plan. Beyond theoretical interest, this framework offers significant practical advantages in network monitoring, specifically for identifying "heavy-hitter" traffic flows in resource-constrained environments like high-speed internet routers.

Methodology

The research operates within a combinatorial minimax framework, seeking to minimize the number of tests required in the worst-case scenario. The authors introduce several key methodological innovations:

  1. Recursive Formulation: The optimal number of tests, $N(n,d)$, is modeled using a recursive equation that respects the nested constraint.
  2. Frame-Segment Structure: A geometric "frame-segment" pattern was discovered in the sequence of $N(n,d)$. For a fixed number of defectives $d$, the required number of tests remains constant over specific population ranges (segments) and increases predictably as $n$ grows.
  3. Closed-Form Solution: By leveraging this geometric structure, the authors derived the optimal group size $M(n,d)$ for each step as a direct function of $n$ and $d$, bypassing the need for exhaustive computational searches.

The algorithm, termed NESTED, is detailed in the pseudocode below.

The NESTED procedure for identifying defective items using quantitative group testing.

To validate the theoretical results, the authors applied the QGT model to network traffic. They used Maximum Likelihood Estimation (MLE) and Sample Mean Estimation (SME) to estimate the number of heavy hitters from noisy packet arrival counts, simulating traffic with both Poisson and Log-Normal distributions to reflect real-world "heavy-tailed" internet traffic.

Key Results and Insights

The proposed nested plan is proven to be order optimal, meaning its performance scales at the same rate as the best possible theoretical plan as the population size approaches infinity. This is particularly important for hardware implementations, as nested plans maintain a simple "tree" structure that is easier to manage than non-nested alternatives.

Performance comparison: Number of tests required by the Nested plan versus the Binary Splitting baseline as the number of defectives $d$ increases.

Key findings from the study include:

  • Efficiency Gains: In heavy-hitter detection simulations ($n=1000$), the QGT approach achieved orders of magnitude better accuracy than industry standards like Sampled NetFlow for the same detection window.
  • Resource Optimization: The QGT approach required hundreds of times fewer counters (memory entries) to achieve the same accuracy as sampling methods, making it ideal for high-speed hardware.
  • Handling Unknown $d$: The authors demonstrated that if the total number of defectives $d$ is unknown, the optimal strategy is to test the entire population first to reveal $d$, then proceed with the nested plan.
  • Symmetry: The problem's inherent symmetry allows the algorithm to efficiently identify non-defective items when they are in the minority, effectively handling cases where $d > n/2$.

Conclusion

This work fills a long-standing gap in group testing theory by providing a closed-form optimal nested test plan. While the "nested" restriction is a constraint, its order-optimality and implementation simplicity make it highly practical. Future work may involve physical hardware implementations (e.g., on FPGA or ASIC) and extending this logic to more complex models, such as Threshold Group Testing or non-stationary traffic patterns.

Summary updated

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 paper, we establish the optimal nested test plan in a 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. Other applications include anomaly detection and wideband spectrum sensing in cognitive radio systems.
BibTeX
@inproceedings{wang2015optimal,
  author = {Chao Wang and Qing Zhao and Chen-Nee Chuah},
  title = {{Optimal Nested Test Plan for Combinatorial Quantitative Group Testing}},
  booktitle = {ITA},
  year = {2015},
  doi = {10.1109/ita.2015.7308980},
}
Figure