Improved Algorithms for Non-adaptive Group Testing with Consecutive Positives

Improved Algorithms for Non-adaptive Group Testing with Consecutive Positives. Bui, T. V., Cheraghchi, M., & Nguyen, T. D. In Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2021.

Paper

Link doi abstract bibtex

The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items that returns positive if the subset contains at least one positive and negative otherwise. In non-adaptive group testing, all tests are independent, can be performed in parallel, and represented as a measurement matrix. In this work, we consider non-adaptive group testing with consecutive positives in which the items are linearly ordered and the positives are consecutive in that order. We present two algorithms for efficiently identifying consecutive positives. In particular, without storing measurement matrices, we can identify up to $d$ consecutive positives with $2 łog_2{\frac{n}{d}} + 2d$ ($4 łog_2{\frac{n}{d}} + 2d$, resp.) tests in $O( łog_2^2{\frac{n}{d}} + d)$ ($O( łog_2{\frac{n}{d}} + d)$, resp.) time. These results significantly improve the state-of-the-art scheme in which it takes $5 łog_2{\frac{n}{d}} + 2d + 21$ tests to identify the positives in $O( \frac{n}{d} łog_2{\frac{n}{d}} + d^2)$ time with the measurement matrices associated with the scheme stored somewhere.

@INPROCEEDINGS{ref:BCN21,
  author =	 {Thach V. Bui and Mahdi Cheraghchi and Thuc
                  D. Nguyen},
  title =	 {Improved Algorithms for Non-adaptive Group Testing
                  with Consecutive Positives},
  year =	 2021,
  booktitle =	 {Proceedings of the {IEEE International Symposium on
                  Information Theory (ISIT)}},
  url_Paper =	 {https://arxiv.org/abs/2101.11294},
  url_Link = {https://ieeexplore.ieee.org/document/9518277},
  doi = {10.1109/ISIT45174.2021.9518277},
  abstract =	 {The goal of group testing is to efficiently identify
                  a few specific items, called positives, in a large
                  population of items via tests. A test is an action
                  on a subset of items that returns positive if the
                  subset contains at least one positive and negative
                  otherwise. In non-adaptive group testing, all tests
                  are independent, can be performed in parallel, and
                  represented as a measurement matrix. In this work,
                  we consider non-adaptive group testing with
                  consecutive positives in which the items are
                  linearly ordered and the positives are consecutive
                  in that order.  We present two algorithms for
                  efficiently identifying consecutive positives. In
                  particular, without storing measurement matrices, we
                  can identify up to $d$ consecutive positives with $2
                  \log_2{\frac{n}{d}} + 2d$ ($4 \log_2{\frac{n}{d}} +
                  2d$, resp.) tests in $O( \log_2^2{\frac{n}{d}} + d)$
                  ($O( \log_2{\frac{n}{d}} + d)$, resp.) time. These
                  results significantly improve the state-of-the-art
                  scheme in which it takes $5 \log_2{\frac{n}{d}} + 2d
                  + 21$ tests to identify the positives in $O(
                  \frac{n}{d} \log_2{\frac{n}{d}} + d^2)$ time with
                  the measurement matrices associated with the scheme
                  stored somewhere. }
}

Downloads: 0

{"_id":"caiLYoksxPPqEstfe","bibbaseid":"bui-cheraghchi-nguyen-improvedalgorithmsfornonadaptivegrouptestingwithconsecutivepositives-2021","author_short":["Bui, T. V.","Cheraghchi, M.","Nguyen, T. D."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Thach","V."],"propositions":[],"lastnames":["Bui"],"suffixes":[]},{"firstnames":["Mahdi"],"propositions":[],"lastnames":["Cheraghchi"],"suffixes":[]},{"firstnames":["Thuc","D."],"propositions":[],"lastnames":["Nguyen"],"suffixes":[]}],"title":"Improved Algorithms for Non-adaptive Group Testing with Consecutive Positives","year":"2021","booktitle":"Proceedings of the IEEE International Symposium on Information Theory (ISIT)","url_paper":"https://arxiv.org/abs/2101.11294","url_link":"https://ieeexplore.ieee.org/document/9518277","doi":"10.1109/ISIT45174.2021.9518277","abstract":"The goal of group testing is to efficiently identify a few specific items, called positives, in a large population of items via tests. A test is an action on a subset of items that returns positive if the subset contains at least one positive and negative otherwise. In non-adaptive group testing, all tests are independent, can be performed in parallel, and represented as a measurement matrix. In this work, we consider non-adaptive group testing with consecutive positives in which the items are linearly ordered and the positives are consecutive in that order. We present two algorithms for efficiently identifying consecutive positives. In particular, without storing measurement matrices, we can identify up to $d$ consecutive positives with $2 łog_2{\\frac{n}{d}} + 2d$ ($4 łog_2{\\frac{n}{d}} + 2d$, resp.) tests in $O( łog_2^2{\\frac{n}{d}} + d)$ ($O( łog_2{\\frac{n}{d}} + d)$, resp.) time. These results significantly improve the state-of-the-art scheme in which it takes $5 łog_2{\\frac{n}{d}} + 2d + 21$ tests to identify the positives in $O( \\frac{n}{d} łog_2{\\frac{n}{d}} + d^2)$ time with the measurement matrices associated with the scheme stored somewhere. ","bibtex":"@INPROCEEDINGS{ref:BCN21,\n author =\t {Thach V. Bui and Mahdi Cheraghchi and Thuc\n D. Nguyen},\n title =\t {Improved Algorithms for Non-adaptive Group Testing\n with Consecutive Positives},\n year =\t 2021,\n booktitle =\t {Proceedings of the {IEEE International Symposium on\n Information Theory (ISIT)}},\n url_Paper =\t {https://arxiv.org/abs/2101.11294},\n url_Link = {https://ieeexplore.ieee.org/document/9518277},\n doi = {10.1109/ISIT45174.2021.9518277},\n abstract =\t {The goal of group testing is to efficiently identify\n a few specific items, called positives, in a large\n population of items via tests. A test is an action\n on a subset of items that returns positive if the\n subset contains at least one positive and negative\n otherwise. In non-adaptive group testing, all tests\n are independent, can be performed in parallel, and\n represented as a measurement matrix. In this work,\n we consider non-adaptive group testing with\n consecutive positives in which the items are\n linearly ordered and the positives are consecutive\n in that order. We present two algorithms for\n efficiently identifying consecutive positives. In\n particular, without storing measurement matrices, we\n can identify up to $d$ consecutive positives with $2\n \\log_2{\\frac{n}{d}} + 2d$ ($4 \\log_2{\\frac{n}{d}} +\n 2d$, resp.) tests in $O( \\log_2^2{\\frac{n}{d}} + d)$\n ($O( \\log_2{\\frac{n}{d}} + d)$, resp.) time. These\n results significantly improve the state-of-the-art\n scheme in which it takes $5 \\log_2{\\frac{n}{d}} + 2d\n + 21$ tests to identify the positives in $O(\n \\frac{n}{d} \\log_2{\\frac{n}{d}} + d^2)$ time with\n the measurement matrices associated with the scheme\n stored somewhere. }\n}\n\n","author_short":["Bui, T. V.","Cheraghchi, M.","Nguyen, T. D."],"key":"ref:BCN21","id":"ref:BCN21","bibbaseid":"bui-cheraghchi-nguyen-improvedalgorithmsfornonadaptivegrouptestingwithconsecutivepositives-2021","role":"author","urls":{" paper":"https://arxiv.org/abs/2101.11294"," link":"https://ieeexplore.ieee.org/document/9518277"},"metadata":{"authorlinks":{}}},"bibtype":"inproceedings","biburl":"http://mahdi.ch/writings/cheraghchi.bib","dataSources":["YZqdBBx6FeYmvQE6D"],"keywords":[],"search_terms":["improved","algorithms","non","adaptive","group","testing","consecutive","positives","bui","cheraghchi","nguyen"],"title":"Improved Algorithms for Non-adaptive Group Testing with Consecutive Positives","year":2021,"downloads":14}