7 Sampling from Data Streams

This chapter motivates sampling as a core task for fast, approximate analytics over massive data streams. It frames streaming models—landmark streams and sliding windows—and explains the goal: maintain small, continually updated samples that enable near-real-time answers with controllable error and small failure probability, all in one pass and with sublinear memory. Building on ideas from database sampling and online aggregation, the text anchors each method in an IP-address fingerprinting use case, emphasizing practical constraints like de-duplication, single-pass processing, and low-latency querying.

For landmark streams, the chapter first covers Bernoulli sampling (and Poisson as a generalized, weighted variant). It highlights a skip-based implementation that reduces calls to pseudo-random generators and notes advantages such as natural parallelizability across substreams, while stressing the drawback of an unbounded, random sample size. Reservoir sampling solves that by keeping a fixed-size simple random sample: early elements fill the reservoir, later ones probabilistically replace existing items. An efficient implementation uses inverse transform sampling, acceptance–rejection, and “squeezing” to jump over non-included elements. The chapter then introduces biased reservoir sampling to favor recency, modeling “residing probability” with an exponential, memoryless decay controlled by a parameter that tunes the speed of aging. It provides bounds on expected sample size, a simple maintenance rule that mixes replacement with appends based on reservoir occupancy, and a throttled variant for tighter memory budgets.

For sliding windows, two specialized methods maintain freshness as items age out. Chain Sampling targets sequence-based windows by running k independent chains: each chain maintains a current item and a preselected successor to inherit the sample exactly when the current one expires, yielding at each moment a sample of size k with replacement using small, bounded memory. Priority Sampling addresses timestamp-based windows by assigning each arrival a random priority; the current sample is the highest-priority item within the window, while a priority-ordered successor list ensures immediate, correct handover at expiration with modest expected memory. A comparative study using an R stream framework shows that biased reservoir sampling adapts quickly to sudden distribution shifts, while standard reservoir sampling lags due to its uniform weighting of old and new data. The chapter closes with guidance on choosing the aging rate to match an application’s effective horizon and notes practical support in R and Python for prototyping and testing streaming samplers.

You can see how first, fourth and eight element of the stream are included in the sample, since the corresponding pseudo-random value uniform on [0,1] turned out less than p=0.3.

: The figure shows the content of the reservoir after each of the first seven arrivals. First three elements are included in the sample deterministically. Subsequently, is skipped (this corresponds to the number of elements to skip, after is included being 1). is then randomly replaces in the reservoir . Next element, is included at the random position 1 in the reservoir, and replaces (notice that this means that was 0). is definitely bigger than 0, since at least one element, , is skipped.

: We can see the balance between probabilities of inclusion (red, longdash line,) and probabilities of “removal up to the time point N=100” (orange, dotdash line) reflected in (black line) being approximately constant for all elements seen so far (when the reservoir is of size 10). This means that each element, no matter when it has been seen, has the same chance of being in the sample.

: Notice that for we need 100 elements to reduce f(i,N) by the factor of 0.36, while for this number is 50. So the higher the , easier it is to forget old elements.

: The figure shows the content of the reservoir for first 7 arrivals under the the biased reservoir sampling strategy.

: Figure shows the content of the chain (list L) for the first 7 elements from a sequence-based windowed stream of size n=3.

: Figure shows content of the list of successors and the current sample for first 6 arrival times in ms for a timestamp-based window of length 600 ms.

Dashed lines (purple and blue) connect sample averages of samples selected using biased reservor sampling. Blue (upper) with and for the purple (lower) dashed line. Dot-dashed lines (red and range) track sample averages at every 100k new elements for two unbiased reservoir sample sizes.

• We have gotten to know five algorithms for sampling from a data stream (three for landmark streams and two for windowed streams). Bernoulli sampling is a very simple and representative sampling algorithm, but if you want to use it, you have to think about some sample size curbing strategy, without introducing much bias.
• Reservoir sampling solved our problem of variable sample size and delivered a SRS from elements seen so far at any moment. If we would want to accentuate more recent elements in our sample, biased reservoir sampling would be one way to go. Here, we need to think about our desired speed of aging factor and how it relates to our available space. This depends on the realistic parameters that you face in your own application.
• The other option to accentuate recently arrived elements in the stream is via sliding window. If we decide that we need to sample from that window due to its size, we learned how to implement chain sampling for sequence-based windows and priority sampling for time-based windows.
• We saw how biased reservoir sampling in our simulation managed to adjust to sudden shift in concept, while reservoir sampling was unable to react to this change, and led to biased answer of the query about the current / recent true average of the stream data. You do need to adjust the speed of aging parameter though, so that it suits notion of sufficient recency for your particular use-case.

FAQ