About: A Fast Binary Splitting Approach to Non-Adaptive Group Testing

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: A Fast Binary Splitting Approach to Non-Adaptive Group Testing Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
title	A Fast Binary Splitting Approach to Non-Adaptive Group Testing
Creator	Price, Eric Scarlett, Jonathan
source	ArXiv
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%22possibly defective%22groups 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.
has issue date	2020-06-18(xsd:dateTime)
has license	arxiv
sha1sum (hex)	181b40a8fb5cd655d3bcc94fc488e8c195d73dd2
resource representing a document's title	A Fast Binary Splitting Approach to Non-Adaptive Group Testing
resource representing a document's body	covid:181b40a8fb5cd655d3bcc94fc488e8c195d73dd2#body_text
is schema:about of	named entity 'provide' named entity 'algorithm' named entity 'adaptive' named entity 'maintaining' named entity 'groups' »more»

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software