www-ai.cs.tu-dortmund.de/LEHRE/FACHPROJEKT/SS12/paper/counting/Arasu2004.pdf
the stream 15, 7, 6, 24, 21, 24, . . .. A fixed-size sliding window over this stream with size N = 3 produces the following sequence of bags: {15}, {15, 7}, {15, 7, 6}, {7, 6, 24}, {6, 24, 21}, {24, 21 [...] for a variable-size window over this stream is the following: {15}, {15, 7}, {7}, {7, 6}, {7, 6, 24}, {7, 6, 24, 21}, {6, 24, 21}, . . .. 2
Fixed- and variable-size sliding windows abstract the essen- tial [...] space, beating the sam-
pling bound. Further improvement in space is possible, as described in Section 6. Recently Cormode and Muthukrish- nan [8] proposed a sketching technique called CM-sketches that can …