Patent Document ID: 20100138529
Application ID: 12325340
Patent Status: 0

Claim One:
1. A method of obtaining a generic sample of an input stream associated with a computer network, the method comprising: (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 a VAR OPT 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 , Σ 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.