Variance-Optimal Sampling-Based Estimation of Subset Sums

A tangible computer-readable carrier comprising instructions configured to cause at least one computing device to obtain a generic sample of an input stream associated with a computer network by:

• (a) generating a sample S from an input stream of items i, the sample S including at most k items i;
• and
• (b) determining whether an nth item i of the input stream should be included in sample S, n=k+1, at most k items i being maintained in sample S, by computing a VAROPTk sample of a set I, the set I including n items i:
• (1) computing a threshold τk such that Σiε[n]min{1, {tilde over (w)}i/τk}=k, {tilde over (w)}i being an adjusted weight of item i;
• (2) including an item i in sample S with probability pi=min{1, {tilde over (w)}i/τk} and dropping an item i with probability qi=1−pi, wherein ΣiεIqi=n−k=1;
• (3) partitioning a unit interval [0,1] into a segment of size qi for each i with qi>0;
• (4) selecting a random point rε[0,1], r being within an interval of dεI, d being a dropped item;
• (5) dropping d and setting sample S=I\{d}, thereby updating sample S;
• and
• (6) setting {tilde over (w)}i=τk for each iεS with {tilde over (w)}i<τk, thereby obtaining a generic sample of the input stream

A system for obtaining a generic sample of an input stream associated with a computer network comprising:

• (a) a generating module configured to generate a sample S from an input stream of items i, the sample S including at most k items i;
• and
• (b) a determination module configured to determine whether an nth item i of the input stream should be included in sample S, n=k+1, at most k items i being maintained in sample S, by computing a VAROPTk sample of a set I, the set I including n items i:
• (1) computing a threshold τk such that Σiε[n]min{1, {tilde over (w)}i/τk}=k, {tilde over (w)}i being an adjusted weight of item i;
• (2) including an item i in Sample S with probability pi=min{1, {tilde over (w)}i/τk} and dropping an item i with probability qi=1−pi, ΣiεIqi=n−k=1;
• (3) partitioning a unit interval [0,1] into a segment of size qi for each i with qi>0;
• (4) selecting a random point rε[0,1], r being within an interval of dεI, d being a dropped item;
• (5) dropping d and setting sample S=I\{d}, thereby updating sample S;
• and
• (6) setting {tilde over (w)}i=τk for each iεS with {tilde over (w)}i<τk, thereby obtaining a generic sample of the input stream