Efficient sampling of non-strict turnstile data streams
We study the problem of generating a large sample from a data stream S S of elements (i,v) ( i , v ) , where i is a positive integer key, v is an integer equal to the count of key i , and the sample consists of pairs (i,Ci) ( i , C i ) for Ci=?(i,v)?Sv C i = ? ( i , v ) ? S v . We consider strict turnstile streams and general non-strict turnstile streams, in which Ci C i may be negative. Our sample is useful for approximating both forward and inverse distribution statistics, within an additive error ?  and provable success probability 1?? 1 ? ? . Our sampling method improves by an order of magnitude the known processing time of each stream element, a crucial factor in data stream applications, thereby providing a feasible solution to the sampling problem. For example, for a sample of size O(??2log?(1/?)) O ( ? ? 2 log ? ( 1 / ? ) ) in non-strict streams, our solution requires O((log?log?(1/?))2+(log?log?(1/?))2) O ( ( log ? log ? ( 1 / ? ) ) 2 + ( log ? log ? ( 1 / ? ) ) 2 ) operations per stream element, whereas the best previous solution requires O(??2log2?(1/?)) O ( ? ? 2 log 2 ? ( 1 / ? ) ) evaluations of a fully independent hash function per element. We achieve this improvement by constructing an efficient K-elements recovery structure from which K  elements can be extracted with probability 1?? 1 ? ? . Our structure enables our sampling algorithm to run on distributed systems and extract statistics on the difference between streams.
sampling data streams inverse distribution