グループテスト
The first thorough treatment of group testing was given by Sobel and Groll in their formative 1959 paper on the subject. They described five new procedures – in addition to generalisations for when the prevalence rate is unknown – and for the most optimal one, they provided an explicit formula for the expected number of tests it would use. The paper also made the connection between group testing and information theory for the first time, as well as discussing several generalisations of the group-testing problem and providing some new applications of the theory.
Algorithms for non-adaptive group testing consist of two distinct phases. First, it is decided how many tests to perform and which items to include in each test. In the second phase, often called the decoding step, the results of each group test are analysed to determine which items are likely to be defective. The first phase is usually encoded in a matrix as follows.
Suppose a non-adaptive group testing procedure for n {\displaystyle n} items consists of the tests S 1 , S 2 , ... , S t {\displaystyle S_{1},S_{2},\dots ,S_{t}} for some t ∈ N ≥ 0 {\displaystyle t\in \mathbb {N} _{\geq 0}} . The testing matrix for this scheme is the t × n {\displaystyle t\times n} binary matrix, M {\displaystyle M} , where ( M ) i j = 1 {\displaystyle (M)_{ij}=1} if and only if j ∈ S i {\displaystyle j\in S_{i}} (and is zero otherwise).
) Group testing can be used to dramatically reduce the number of hashes that need to be stored. A test becomes a comparison between the stored and current hashes, which is positive when there is a mismatch. This indicates that at least one edited datum (which is taken as defectiveness in this model) is contained in the group that generated the current hash.
In fact, the amount of hashes needed is so low that they, along with the testing matrix they refer to, can even be stored within the organisational structure of the data itself. This means that as far as memory is concerned the test can be performed 'for free'. (This is true with the exception of a master-key/password that is used to secretly determine the hashing function.)
On the other hand, if no one in the pool has syphilis then many tests are saved, since every soldier in that group can be eliminated with just one test.
The items that cause a group to test positive are generally called defective items (these are the broken lightbulbs, syphilitic men, etc.). Often, the total number of items is denoted as n {\displaystyle n} and d {\displaystyle d} represents the number of defectives if it is assumed to be known.
↑ The original problem that Dorfman studied was of this nature (although he did not account for this), since in practice, only a certain number of blood sera could be pooled before the testing procedure became unreliable. This was the main reason that Dorfman’s procedure was not applied at the time.
↑ However, as is often the case in mathematics, group testing has been subsequently re-invented multiple times since then, often in the context of applications. For example, Hayes independently came up with the idea to query groups of users in the context of multiaccess communication protocols in 1978.
↑ This is sometimes referred to as the Hu-Hwang-Wang conjecture.
That is, if and only if at least one defective item was included in the i -th {\displaystyle i{\textrm {-th}}} test.
↑ This kind of measurement comes up in many applications. For example, certain kinds of digital camera or MRI machines, where time constraints require that only a small number of measurements are taken.
↑ More formally hashes have a property called collision resistance, which is that the likelihood of the same hash resulting from different inputs is very low for data of an appropriate size. In practice, the chance that two different inputs might produce the same hash is often ignored.