Efficient (nonrandom) Construction and Decoding for Non-adaptive Group Testing

• Item type: Journal(1)
• 公開日: 2019-03-15
• タイトル: Efficient (nonrandom) Construction and Decoding for Non-adaptive Group Testing
• タイトル / 言語: en
• タイトル: Efficient (nonrandom) Construction and Decoding for Non-adaptive Group Testing
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：若手研究者] non-adaptive group testing, Nonrandom construction, Efficient decoding, Combinatorics
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: SOKENDAI (The Graduate University for Advanced Studies)
• 著者所属: Graduate School of Natural Science and Technology, Okayama University
• 著者所属: National Institute of Technology, Tokyo College
• 著者所属: New Jersey Institute of Technology
• 著者所属: National Institute of Informatics
• 著者所属(英): en
• 著者所属(英): SOKENDAI (The Graduate University for Advanced Studies)
• 著者所属(英): en
• 著者所属(英): Graduate School of Natural Science and Technology, Okayama University
• 著者所属(英): en
• 著者所属(英): National Institute of Technology, Tokyo College
• 著者所属(英): en
• 著者所属(英): New Jersey Institute of Technology
• 著者所属(英): en
• 著者所属(英): National Institute of Informatics
• 著者名: Thach, V. Bui; Minoru, Kuribayashi; Tetsuya, Kojima; Roghayyeh, Haghvirdinezhad; Isao, Echizen
• 著者名(英): Thach, V. Bui; Minoru, Kuribayashi; Tetsuya, Kojima; Roghayyeh, Haghvirdinezhad; Isao, Echizen
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: The task of non-adaptive group testing is to identify up to d defective items from N items, where a test is positive if it contains at least one defective item, and negative otherwise. If there are t tests, they can be represented as a t × N measurement matrix. We have answered the question of whether there exists a scheme such that a larger measurement matrix, built from a given t × N measurement matrix, can be used to identify up to d defective items in time O(t log2 N). In the meantime, a t × N nonrandom measurement matrix with $t = O \left(\frac{d^2 \log_2^2{N}}{(\log_2(d\log_2{N}) - \log_2{\log_2(d\log_2{N})})^2} \right)$ can be obtained to identify up to d defective items in time poly(t). This is much better than the best well-known bound, $t = O \left(d^2 \log_2^2{N} \right)$. For the special case d = 2, there exists an efficient nonrandom construction in which at most two defective items can be identified in time $4\log_2^2{N}$ using $t = 4\log_2^2{N}$ tests. Numerical results show that our proposed scheme is more practical than existing ones, and experimental results confirm our theoretical analysis. In particular, up to 27 = 128 defective items can be identified in less than 16 s even for N = 2100.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.27(2019) (online); DOI http://dx.doi.org/10.2197/ipsjjip.27.245; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The task of non-adaptive group testing is to identify up to d defective items from N items, where a test is positive if it contains at least one defective item, and negative otherwise. If there are t tests, they can be represented as a t × N measurement matrix. We have answered the question of whether there exists a scheme such that a larger measurement matrix, built from a given t × N measurement matrix, can be used to identify up to d defective items in time O(t log2 N). In the meantime, a t × N nonrandom measurement matrix with $t = O \left(\frac{d^2 \log_2^2{N}}{(\log_2(d\log_2{N}) - \log_2{\log_2(d\log_2{N})})^2} \right)$ can be obtained to identify up to d defective items in time poly(t). This is much better than the best well-known bound, $t = O \left(d^2 \log_2^2{N} \right)$. For the special case d = 2, there exists an efficient nonrandom construction in which at most two defective items can be identified in time $4\log_2^2{N}$ using $t = 4\log_2^2{N}$ tests. Numerical results show that our proposed scheme is more practical than existing ones, and experimental results confirm our theoretical analysis. In particular, up to 27 = 128 defective items can be identified in less than 16 s even for N = 2100.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.27(2019) (online); DOI http://dx.doi.org/10.2197/ipsjjip.27.245; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 60, 号 3, 発行日 2019-03-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764