Patent Document ID: 8005949
Application ID: 12325340
Patent Status: 1

Claim One:
1. A non-transitory computer-readable carrier comprising instructions configured to cause at least one computing device to obtain a generic sample of an input stream of packets associated with a computer network to estimate a total weight of a subset of the input stream using the generic sample 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 n th 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 VAROPT k ([n]), which is a VAROPT k sample of a set I, the set I including n items i, by: (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 item i in sample S with probability p i =min{1, {tilde over (w)} i /τ k } and dropping item i with probability q i =1−p i , wherein Σ iεI q i =n−k=1; (3) partitioning a unit interval [0,1] into a segment of size q i for each i with q i >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, wherein average variance (V m ) of weight estimates is simultaneously minimized over a plurality of subsets of the input stream, and wherein ΣV and VΣ are minimized such that ∑ V = ∑ i ∈ [ n ] ⁢ Var ⁡ [ w ^ i ] ⁢ ⁢ = nV 1 ⁢ and ⁢ V ∑ = Var [ ∑ i ∈ [ n ] ⁢ w ^ i ] ⁢ ⁢ = Var ⁡ [ w ^ [ n ] ] ⁢ ⁢ = V n. wherein ΣV is a sum of individual variances, VΣ is a variance of the estimate of total.