Document Open Access Logo

A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Authors Eric Price, Jonathan Scarlett

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2020.13.pdf
  • Filesize: 0.57 MB
  • 20 pages

Document Identifiers

Author Details

Eric Price
  • Department of Computer Science, University of Texas at Austin, TX, USA
Jonathan Scarlett
  • Department of Computer Science & Department of Mathematics, National University of Singapore, Singapore

Funding

  • Price, Eric: Supported in part by NSF Award CCF-1751040 (CAREER).
  • Scarlett, Jonathan: Supported by an NUS Early Career Research Award.

Cite AsGet BibTex

Eric Price and Jonathan Scarlett. A Fast Binary Splitting Approach to Non-Adaptive Group Testing. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.13

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² log k ⋅ 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 Ω(n) storage, we also provide a low-storage variant based on hashing, with similar recovery guarantees.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Group testing
  • sparsity
  • sublinear-time decoding
  • binary splitting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Matthew Aldridge. The capacity of Bernoulli nonadaptive group testing. IEEE Transactions on Information Theory, 63(11):7142-7148, 2017. Google Scholar
  2. Matthew Aldridge. Individual testing is optimal for nonadaptive group testing in the linear regime. IEEE Transactions on Information Theory, 65(4):2058-2061, April 2019. Google Scholar
  3. Matthew Aldridge, Leonardo Baldassini, and Oliver Johnson. Group testing algorithms: Bounds and simulations. IEEE Transactions on Information Theory, 60(6):3671-3687, June 2014. Google Scholar
  4. Matthew Aldridge, Oliver Johnson, and Jonathan Scarlett. Group testing: An information theory perspective. Foundations and Trends in Communications and Information Theory, 15(3-4):196-392, 2019. Google Scholar
  5. George K. Atia and Venkatesh Saligrama. Boolean compressed sensing and noisy group testing. IEEE Transactions on Information Theory, 58(3):1880-1901, March 2012. Google Scholar
  6. Leonardo Baldassini, Oliver Johnson, and Matthew Aldridge. The capacity of adaptive group testing. In IEEE International Symposium on Information Theory, pages 2676-2680, July 2013. Google Scholar
  7. Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 13(7):422-426, 1970. Google Scholar
  8. Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao. Cross-sender bit-mixing coding. In International Conference on Information Processing in Sensor Networks, 2019. Google Scholar
  9. Steffen Bondorf, Binbin Chen, Jonathan Scarlett, Haifeng Yu, and Yuda Zhao. Sublinear-time non-adaptive group testing with O(k log n) tests via bit-mixing coding, 2019. URL: http://arxiv.org/abs/1904.10102.
  10. Sheng Cai, Mohammad Jahangoshahi, Mayank Bakshi, and Sidharth Jaggi. Efficient algorithms for noisy group testing. IEEE Transactions on Information Theory, 63(4):2113-2136, 2017. Google Scholar
  11. Chun Lam Chan, Sidharth Jaggi, Venkatesh Saligrama, and Samar Agnihotri. Non-adaptive group testing: Explicit bounds and novel algorithms. IEEE Transactions on Information Theory, 60(5):3019-3035, May 2014. Google Scholar
  12. Mahdi Cheraghchi. Noise-resilient group testing: Limitations and constructions. In International Symposium on Fundamentals of Computation Theory, pages 62-73, 2009. Google Scholar
  13. Mahdi Cheraghchi and Vasileios Nakos. Combinatorial group testing and sparse recovery schemes with near-optimal decoding time, 2020. URL: http://arxiv.org/abs/2006.08420.
  14. Raphaël Clifford, Klim Efremenko, Ely Porat, and Amir Rothschild. Pattern matching with don't cares and few errors. Journal of Computer and System Sciences, 76(2):115-124, 2010. Google Scholar
  15. Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Information-theoretic and algorithmic thresholds for group testing. In International Colloquium on Automata, Languages and Programming, 2019. Google Scholar
  16. Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Optimal group testing, 2020. URL: http://arxiv.org/abs/1911.02287.
  17. Graham Cormode and S. Muthukrishnan. An improved data stream summary: the count-min sketch and its applications. Journal of Algorithms, 55(1):58-75, 2005. Google Scholar
  18. Graham Cormode and S. Muthukrishnan. What’s hot and what’s not: Tracking most frequent items dynamically. ACM Transactions on Database Systems, 30(1):249-278, March 2005. Google Scholar
  19. Robert Dorfman. The detection of defective members of large populations. Annals of Mathematical Statistics, 14(4):436-440, 1943. Google Scholar
  20. Dingzhu Du and Frank K. Hwang. Combinatorial group testing and its applications, volume 12. World Scientific, 2000. Google Scholar
  21. Meyer Dwass. The total progeny in a branching process and a related random walk. Journal of Applied Probability, 6(3):682-686, 1969. Google Scholar
  22. Arkadii G. D'yachkov and Vladimir V. Rykov. A survey of superimposed code theory. Problems of Control and Information, 12(4):1-13, 1983. Google Scholar
  23. Arkady D'yachkov, Ilya Vorobyev, Nikita Polianskii, and Vladislav Shchukin. Bounds on the rate of superimposed codes. In IEEE International Symposium on Information Theory, June 2014. Google Scholar
  24. William Feller. An introduction to probability theory and its applications. Wiley, 1957. Google Scholar
  25. Antonio Fernández Anta, Miguel A. Mosteiro, and Jorge Ramón Muñoz. Unbounded contention resolution in multiple-access channels. In Distributed Computing, volume 6950, pages 225-236. Springer Berlin Heidelberg, 2011. Google Scholar
  26. Anna C. Gilbert, Mark A. Iwen, and Martin J. Strauss. Group testing and sparse signal recovery. In Asilomar Conference on Signals, Systems, and Computers, pages 1059-1063, October 2008. Google Scholar
  27. Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, and Roman Vershynin. One sketch for all: Fast algorithms for compressed sensing. In ACM-SIAM Symposium on Discrete Algorithms, pages 237-246, New York, 2007. Google Scholar
  28. Catherine A. Hogan, Malaya K. Sahoo, and Benjamin A. Pinsky. Sample pooling as a strategy to detect community transmission of SARS-CoV-2. Journal of the American Medical Association, April 2020. Google Scholar
  29. Frank K. Hwang. A method for detecting all defective members in a population by group testing. Journal of the American Statistical Association, 67(339):605-608, 1972. Google Scholar
  30. Huseyin A. Inan, Peter Kairouz, Mary Wootters, and Ayfer Ozgur. On the optimality of the Kautz-Singleton construction in probabilistic group testing. IEEE Transactions on Information Theory, 65(9):5592-5603, September 2019. Google Scholar
  31. Piotr Indyk, Hung Q. Ngo, and Atri Rudra. Efficiently decodable non-adaptive group testing. In ACM-SIAM Symposium on Discrete Algorithms, 2010. Google Scholar
  32. Piotr Indyk and Eric Price. K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. In ACM Symposium on Theory of Computing, pages 627-636, 2011. Google Scholar
  33. Oliver Johnson, Matthew Aldridge, and Jonathan Scarlett. Performance of group testing algorithms with near-constant tests-per-item. IEEE Transactions on Information Theory, 65(2):707-723, February 2019. Google Scholar
  34. Kangwook Lee, Ramtin Pedarsani, and Kannan Ramchandran. SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes. IEEE Transactions on Signal Processing, 67(17):4649-4664, September 2019. Google Scholar
  35. M. B. Malyutov and P. S. Mateev. Screening designs for non-symmetric response function. Mathematical Notes of the Academy of Sciences of the USSR, 29:109-127, 1980. Google Scholar
  36. Mikhail B. Malyutov. The separating property of random matrices. Mathematical Notes of the Academy of Sciences of the USSR, 23(1):84-91, 1978. Google Scholar
  37. Hung Q. Ngo, Ely Porat, and Atri Rudra. Efficiently decodable error-correcting list disjunct matrices and applications. In International Colloquium on Automata, Languages and Programming, 2011. Google Scholar
  38. Ely Porat and Amir Rothschild. Explicit nonadaptive combinatorial group testing schemes. IEEE Transactions on Information Theory, 57(12):7982-7989, 2011. Google Scholar
  39. Jonathan Scarlett and Volkan Cevher. Phase transitions in group testing. In ACM-SIAM Symposium on Discrete Algorithms, 2016. Google Scholar
  40. Alan Siegel. On universal classes of fast high performance hash functions, their time-space tradeoff, and their applications. In IEEE Symposium on Foundations of Computer Science, 1989. Google Scholar
  41. Mikkel Thorup. Fast and powerful hashing using tabulation. Communications of the ACM, 60(7):94-101, 2017. Google Scholar
  42. Claudio M Verdun, Tim Fuchs, Pavol Harar, Dennis Elbrächter, David S Fischer, Julius Berner, Philipp Grohs, Fabian J Theis, and Felix Krahmer. Group testing for SARS-CoV-2 allows for up to 10-fold efficiency increase across realistic scenarios and testing strategies. URL: https://www.medrxiv.org/content/10.1101/2020.04.30.20085290v2, 2020.
  43. Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices, 2010. URL: http://arxiv.org/abs/1011.3027.
  44. Mark N. Wegman and J. Lawrence Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22(3):265-279, 1981. Google Scholar
  45. Idan Yelin, Noga Aharony, Einat Shaer-Tamar, Amir Argoetti, Esther Messer, Dina Berenbaum, Einat Shafran, Areen Kuzli, Nagam Gandali, Tamar Hashimshony, Yael Mandel-Gutfreund, Michael Halberthal, Yuval Geffen, Moran Szwarcwort-Cohen, and Roy Kishony. Evaluation of COVID-19 RT-qPCR test in multi-sample pools. URL: https://www.medrxiv.org/content/early/2020/03/27/2020.03.26.20039438, 2020.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact