4 ms·

Just curious, can you expand a bit on the analysis? I see that by binary search you get O(log(S)) to identify a single positive, and naively rerunning search fr

by mxwsn 7y ago

Just curious, can you expand a bit on the analysis? I see that by binary search you get O(log(S)) to identify a single positive, and naively rerunning search from the beginning P times yields O(P*log(S)). One can certainly do better by avoiding redundant tests but at some point one needs to start reasoning about the distribution of the positives in the samples and I'm not sure how to do that.

daef 7y ago
See https://youtu.be/GqAdVQeIXA0 https://youtu.be/GqAdVQeIXA0 for an explanation: starting at around 30% probability pooling stops making sense.
mxwsn 7y ago
Thought about it overnight and this is what I have: To reason about the distribution of positives in the sample, we consider two limiting cases, then interpolate between them. The cases are: 1. All positives are clustered exactly together. We start with log(S/P) queries to find the parent node of all positives, then test every node in the subtree with 2P-1 queries to identify all positives. In total, this is O(p + log(S/P)). 2. All positives are uniformly distributed. By the pigeonhole principle, the lowest level where every node tests positive must occur at log(P). Above this level, every node tests positive, so we must perform 2P-1 tests. Every P nodes on the level must be binary searched; each node has a subtree of height log(S/P), for Plog(S/P) operations. In total, this is O(P + Plog(S/P)) = O(Plog(S/P)). It is not immediately obvious that the worst case distribution is either case 1 or 2. To address this, we define an interpolation variable K in [0, 1] which describes a distribution where all positives begin clustered together, then KP positives are adversarially moved elsewhere. We claim that K = 0 is case 1 and K = 1 is case 2. Consider the case where KP = 1. As in case 1, we need 2P-1 + log(S/P) tests to fully identify the cluster; we also need a single binary search starting at the 2nd level corresponding to the other half of S, which takes log(S) - 1 operations, for a total of 2P-1+log(S/P)+log(S)-1. As KP increases, the level at which we transition from testing every node to initiating binary search on a node will decrease; as an example, when KP = 4, we fully test halves, then quarters, and then begin binary search. In general, we will need KPlog(S/KP) queries for all binary searches. Finally, no matter what KP is, we need no more than O(P) queries for subtrees where we need to test every node. This yields O(P + KPlog(S/KP)) This allows us to navigate around an adversary choosing the worst distribution of positives possible by taking the upper bound where K = 1, yielding O(P + Plog(S/P)) = O(Plog(S/P)), though this bound is not expected to be tight.

by mxwsn 7y ago

daef 7y ago

See https://youtu.be/GqAdVQeIXA0 https://youtu.be/GqAdVQeIXA0 for an explanation: starting at around 30% probability pooling stops making sense.

mxwsn 7y ago

Thought about it overnight and this is what I have: To reason about the distribution of positives in the sample, we consider two limiting cases, then interpolate between them. The cases are: 1. All positives are clustered exactly together. We start with log(S/P) queries to find the parent node of all positives, then test every node in the subtree with 2P-1 queries to identify all positives. In total, this is O(p + log(S/P)). 2. All positives are uniformly distributed. By the pigeonhole principle, the lowest level where every node tests positive must occur at log(P). Above this level, every node tests positive, so we must perform 2P-1 tests. Every P nodes on the level must be binary searched; each node has a subtree of height log(S/P), for Plog(S/P) operations. In total, this is O(P + Plog(S/P)) = O(Plog(S/P)). It is not immediately obvious that the worst case distribution is either case 1 or 2. To address this, we define an interpolation variable K in [0, 1] which describes a distribution where all positives begin clustered together, then KP positives are adversarially moved elsewhere. We claim that K = 0 is case 1 and K = 1 is case 2. Consider the case where KP = 1. As in case 1, we need 2P-1 + log(S/P) tests to fully identify the cluster; we also need a single binary search starting at the 2nd level corresponding to the other half of S, which takes log(S) - 1 operations, for a total of 2P-1+log(S/P)+log(S)-1. As KP increases, the level at which we transition from testing every node to initiating binary search on a node will decrease; as an example, when KP = 4, we fully test halves, then quarters, and then begin binary search. In general, we will need KPlog(S/KP) queries for all binary searches. Finally, no matter what KP is, we need no more than O(P) queries for subtrees where we need to test every node. This yields O(P + KPlog(S/KP)) This allows us to navigate around an adversary choosing the worst distribution of positives possible by taking the upper bound where K = 1, yielding O(P + Plog(S/P)) = O(Plog(S/P)), though this bound is not expected to be tight.