A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Eric Price, Jonathan Scarlett

Abstract

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of $n$ items and $k$ defectives, we provide an algorithm attaining high-probability recovery with $O(k \log n)$ scaling in both the number of tests and runtime, improving on the best known $O(k^2 \log k \cdot \log n)$ runtime previously available for any algorithm that only uses $O(k \log n)$ tests. Our algorithm bears resemblance to Hwang's adaptive generalized binary splitting algorithm; we recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of "possibly defective" groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires $\Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.

Introduction

Group testing is a technique used to identify a small subset of $k$ defective items within a large population of $n$ items by testing pools of samples. In the non-adaptive setting, all test pools are determined before any results are observed, which is critical for high-throughput applications like medical screening where tests must run in parallel. While the information-theoretic lower bound for the number of tests is $O(k \log n)$, the computational challenge has been the decoding time. Previous algorithms often required time scaling linearly with $n$ or quadratically with $k$, creating a bottleneck for large-scale applications.

Methods: Non-Adaptive Binary Splitting

The proposed algorithm introduces a non-adaptive version of binary splitting. It organizes the population into a virtual binary tree where the root represents the entire set and leaves represent individual items.

Visualization of the binary splitting process across levels.

By performing randomized pooling at each level of the tree simultaneously, the algorithm avoids the need for sequential feedback. The decoder traverses the tree after all results are in: if a group (node) tests negative, the entire branch is pruned. The authors prove that by using $O(k)$ tests per level, the number of "false positive" branches remains small, keeping the total decoding work to $O(k \log n)$. To address memory constraints, the authors also present a variant using $k$-wise independent hashing, which avoids storing the full test matrix.

Performance and Comparison

The algorithm achieves the optimal test complexity of $O(k \log n)$ while simultaneously reaching a decoding time of $O(k \log n)$. This is a significant improvement over the state-of-the-art, as shown in the comparison table below.

Comparison of the proposed algorithm against state-of-the-art methods.

Compared to previous methods like BMC [9], which also uses $O(k \log n)$ tests but requires $O(k^2 \log k \cdot \log n)$ decoding time, the proposed approach offers a linear speedup with respect to the number of defectives. This makes the algorithm particularly suitable for scenarios where $k$ is large relative to the population.

Conclusion

By parallelizing the logic of adaptive binary splitting, this work provides a highly efficient solution for non-adaptive group testing. The algorithm matches theoretical lower bounds for test counts while providing the fastest known decoding time for this class of problems. Future work will focus on extending these guarantees to noisy environments and improving error probabilities for small $k$.

Summary updated

Abstract

In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of $n$ items and $k$ defectives, we provide an algorithm attaining high-probability recovery with $O(k \log n)$ scaling in both the number of tests and runtime, improving on the best known $O(k^2 \log k \cdot \log n)$ runtime previously available for any algorithm that only uses $O(k \log n)$ tests. Our algorithm bears resemblance to Hwang's adaptive generalized binary splitting algorithm (Hwang, 1972); we recursively work with groups of items of geometrically vanishing sizes, while maintaining a list of "possibly defective" groups and circumventing the need for adaptivity. While the most basic form of our algorithm requires $\Omega(n)$ storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.
BibTeX
@inproceedings{price2020fast,
  author = {Eric Price and Jonathan Scarlett},
  title = {{A Fast Binary Splitting Approach to Non-Adaptive Group Testing}},
  booktitle = {APPROX-RANDOM},
  year = {2020},
  url = {https://openreview.net/forum?id=SaMNMxj1Pgc},
}
Figure