How to (Accurately) Skip Past Streams

Overview

For processing massive data streams, most proposed algorithmic methods look at each new item, perform a small number of operations while keeping a small amount of memory, and still perform much-needed analyses on streams. However, in many situations, the update speed per item is very critical and not every stream item can be extensively examined. In practice, this has been addressed by sampling only a subset of items (say 1 in N) from the input, but it results in loss of guarantees on the accuracy of the post-hoc analyses. This paper presents a technique of skipping past streams.