Streaming Data Structures and Sketches

Introduction

Modern systems generate data continuously: clicks, sensor readings, network packets, transactions, search queries, and model predictions. In many applications the stream is too large, too fast, or too persistent to store and scan repeatedly. A streaming data structure processes each item once, or a small number of times, while maintaining a compact summary that supports approximate queries.

The central design problem is a three-way trade-off among memory, accuracy, and update/query time. Exact answers may require storage proportional to the number of distinct events or keys. Sketches deliberately accept bounded error in exchange for fixed or sublinear memory and rapid updates. They are therefore fundamental to observability platforms, fraud detection, recommendation systems, network measurement, database engines, and online machine learning.

Learning Objectives

By the end of this chapter, the reader should be able to:

1. Explain the streaming model and distinguish exact structures from probabilistic summaries.
2. Design and analyze reservoir sampling algorithms.
3. Use Count-Min Sketch for frequency estimation and quantify its error.
4. Explain HyperLogLog cardinality estimation and its statistical behavior.
5. Compare quantile sketches and select an appropriate method.
6. Detect heavy hitters using sketches and candidate-maintenance methods.
7. Engineer real-time summaries under bounded memory, concurrency, and mergeability constraints.
8. Evaluate privacy, bias, reproducibility, and operational risks in approximate analytics.

1. The Streaming Model

A stream is a sequence a₁, a₂, ..., a_n arriving over time. The stream may be unbounded, so an algorithm should generally use memory independent of n, or dependent only logarithmically on it. A one-pass algorithm receives each item once and cannot assume that past items can be revisited.

A streaming algorithm is commonly characterized by:

• Update time: work required per arriving item.
• Query time: work required to answer a question.
• Space: memory consumed, often expressed in words or bytes.
• Error guarantee: deterministic, probabilistic, or empirical.
• Mergeability: whether summaries from partitions can be combined correctly.
• Window semantics: whether results concern all history, a time window, or a decayed recent history.

The distinction between frequency and cardinality is important. Frequency asks how often a particular key occurs; cardinality asks how many distinct keys have occurred. Quantiles ask about the distribution of numeric values, while sampling attempts to retain representative observations.

Approximation must be stated precisely. A statement such as “the answer is accurate” is inadequate unless it specifies an additive or multiplicative error, a confidence probability, and the distributional or hash-function assumptions.

2. Reservoir Sampling

2.1 Problem and intuition

Suppose a stream has unknown length and an algorithm must retain a uniform random sample of k items using only O(k) memory. Storing the first k items is not uniform: later observations have zero probability of selection. Reservoir sampling solves this problem in one pass.

2.2 Algorithm R

For a stream indexed from 1:

1. Place the first k items into the reservoir.
2. For item i, where i > k, draw j uniformly from {1, 2, …, i}.
3. If j ≤ k, replace reservoir position j with item i. Otherwise discard the item.

Pseudocode:

reservoir = first k items
for i = k+1, k+2, ...:
    j = UniformInteger(1, i)
    if j <= k:
        reservoir[j] = item_i

2.3 Correctness

After processing i items, each item has probability k/i of appearing in the reservoir. For an old item, its probability is

A simpler argument is that an old item survives with probability k/(i−1) in the previous reservoir and is not replaced, while the new item is selected with probability k/i. These probabilities establish uniformity by induction. The displayed decomposition separates the cases in which the new item is not selected and is selected into the relevant position; operationally, the established invariant is that every item has probability k/i.

The algorithm assumes a reliable unbiased random-integer generator. Poor randomness can create systematic sampling bias. If the stream ends at n, each item has final inclusion probability k/n, provided n ≥ k.

2.4 Weighted and stratified variants

Uniform sampling is not always appropriate. In weighted reservoir sampling, item i receives a nonnegative priority based on its weight w_i, and the highest priorities are retained. Such methods can provide inclusion probabilities proportional to importance, but their exact implementation and estimators must account for unequal probabilities.

Stratified sampling maintains separate reservoirs for categories such as region, device type, or customer segment. This improves representation of small but important groups, although it allocates memory away from globally frequent groups. Sampling from a changing distribution also raises a temporal issue: a uniform sample over all history may be inappropriate when recent behavior matters. Time-decayed or sliding-window sampling is then preferable.

3. Count-Min Sketch

3.1 Structure

Count-Min Sketch (CMS) estimates frequencies in a stream of keys. It consists of a table with d rows and w counters per row, together with one independent hash function per row. On receiving key x, increment

To estimate the frequency of key x, return

All counters are nonnegative for insertion-only streams. Collisions can only increase a counter, so f̂(x) ≥ f(x): CMS has no underestimation in this setting.

3.2 Error guarantee

Let N be the total number of updates. If each hash function is sufficiently independent and the table width is chosen as

and depth as

then, for a fixed query key, with probability at least 1−δ,

Together with the non-underestimation property, this gives

Here ε is the additive error fraction and δ is the failure probability. The guarantee is additive, not relative. For a very rare key, an additive error of εN may be large relative to its true frequency. The result applies to insertion-only or appropriately adapted signed-update settings; naïvely using nonnegative CMS for deletions destroys the simple one-sided guarantee.

The space is O((1/ε) ln(1/δ)) counters and update time is O(ln(1/δ)). If counters use b bytes, approximate table storage is bwd bytes, excluding hash-function state.

3.3 Worked example

Assume N = 1,000,000, ε = 0.001, and δ = 0.01. Then

w = ⌈e/0.001⌉ = 2719 and d = ⌈ln(100)⌉ = 5.

The guarantee is that a fixed queried key is overestimated by at most 0.001 × 1,000,000 = 1,000 with probability at least 0.99. With four-byte counters, the table requires approximately 2719 × 5 × 4 = 54,380 bytes, apart from metadata. This is dramatically smaller than storing a counter for every possible key, but the error may be unacceptable when decisions depend on differences of only a few events.

3.4 Design choices and limitations

A conservative update improves estimates for some query distributions by incrementing only minimum-valued cells, but it may complicate merge semantics and implementation. Counter overflow must be prevented through sufficiently wide counters, saturation, or periodic rebuilding. Hash independence is an assumption rather than a magical property: correlated or adversarially chosen keys can increase collisions. Secret, periodically changed hash seeds are useful when inputs may be malicious.

CMS can be merged by element-wise addition when two sketches have identical dimensions and compatible hash functions. This property supports distributed counting. However, merging summaries with different parameters is invalid unless a principled conversion or common configuration is used.

4. HyperLogLog for Distinct Counting

4.1 Problem

Let D denote the number of distinct elements in a stream. Exact distinct counting requires storing the set, potentially using memory proportional to D. HyperLogLog (HLL) estimates D with approximately fixed memory.

4.2 Estimator

A hash function maps each item to a sufficiently uniform binary value. Use the first p bits to choose one of m = 2^p registers. Let ρ be one plus the position of the first 1 in the remaining bits, with a suitable convention for an all-zero suffix. Register M_j stores the maximum observed ρ for bucket j.

The raw estimator is

where α_m is a bias-correction constant depending on m. A commonly used approximation for sufficiently large m is α_m ≈ 0.7213/(1 + 1.079/m). Implementations often apply small-range and large-range corrections, so the raw expression should not be treated as a complete production algorithm.

For small estimates, if [[MATH{V}]] registers are zero, linear counting uses

when [[MATH{V > 0}]]. This correction is based on the probability that a register remains empty and is especially useful when the cardinality is not much larger than the number of registers.

Under standard hashing assumptions, HLL’s relative standard error is approximately

Thus increasing the number of registers reduces relative error at a square-root rate. For example, m = 16,384 gives an approximate relative standard error of 1.04/128 = 0.008125, or 0.8125%, before implementation-specific bias and range corrections.

4.3 Properties

HLL stores only a small integer per register and is mergeable: the union of two sketches is obtained by taking the register-wise maximum. This is exactly appropriate for set union under compatible hashing. It is not generally appropriate for set intersection; intersection requires additional methods such as inclusion–exclusion and can have substantially higher error.

HLL estimates distinctness, not frequencies. Repeated occurrences of an item do not continue increasing its contribution after the relevant register has reached its maximum. Hash quality is crucial, and an adversary who can manipulate hashes may bias results.

5. Quantile Sketches

5.1 Quantiles and rank

For numeric observations, the q-quantile is a value whose rank is approximately qN, where 0 ≤ q ≤ 1. The median corresponds to q = 0.5, and the 0.99 quantile is often used for latency objectives.

A rank-error guarantee of ε means that the reported value has rank between approximately (q−ε)N and (q+ε)N, subject to the sketch’s definition and boundary conventions. This differs from value error: a small rank error can correspond to a large value error in a sparse or heavy-tailed distribution.

5.2 Main families

Greenwald–Khanna (GK). GK maintains a sorted compact summary with deterministic rank-error guarantees in a one-pass setting. It is attractive when deterministic bounds matter, but insertion and compression can be more expensive than randomized alternatives.

KLL. The KLL sketch uses randomized compaction levels. It provides strong rank accuracy with excellent space efficiency and is widely used in modern systems. Its guarantees are probabilistic and depend on randomization and implementation details.

t-digest. A t-digest clusters values into centroids, allocating more resolution near tails. It is useful for extreme quantiles and has practical mergeability, but its accuracy guarantees are less uniform and depend on distribution, compression parameters, and implementation.

DDSketch. DDSketch maps positive values logarithmically into bins. It provides a relative-error guarantee for values over an appropriate positive range, making it useful for latency and size measurements. It is not a generic substitute for rank-based sketches and requires careful handling of zero and negative values.

5.3 Operational interpretation

A p99 estimate should not be presented without its time window, population definition, and error interpretation. A service may report p99 latency of 240 ms while the sketch’s rank uncertainty is ±0.001; this does not mean the numerical value is ±0.001 ms. In distributed systems, sketches should be merged only according to their documented merge operation. Averaging separately computed quantiles is generally invalid.

6. Heavy Hitters

A heavy hitter is an item whose frequency is unusually large. A common threshold definition identifies key x when f(x) ≥ φN, where φ is a chosen fraction of total updates. Heavy hitters are used to identify popular products, dominant error codes, abusive IP addresses, and high-volume model features.

6.1 Counter-based methods

The Misra–Gries algorithm maintains at most k−1 counters. For each item, it increments its counter if present, creates a counter if space exists, and otherwise decrements all counters, deleting zeros. At the end, any item with frequency above approximately N/k must appear among the candidates. The counters provide lower-bound-like information, but exact final frequencies require a second pass or another counting mechanism.

The Space-Saving algorithm maintains k entries. On a new key when the table is full, it replaces a minimum-count entry and assigns an estimate based on the previous minimum. It is often effective for top-k monitoring, but its estimates and error interpretation differ from CMS.

6.2 Combining sketches and candidates

CMS can estimate frequencies for a candidate set, but CMS alone does not automatically reveal which keys to query: the universe may be enormous. Practical heavy-hitter systems therefore combine a candidate mechanism, sampling, hierarchical keys, or an external list with a frequency sketch. A two-stage design might use sampling to discover candidates and CMS to refine their counts.

Heavy-hitter thresholds must account for false positives and false negatives. A conservative policy may alert only when the estimated frequency exceeds [[MATH{(φ+ε)N}]], reducing false alarms at the cost of delayed detection. Alerting systems should also define hysteresis so that a key does not repeatedly cross a threshold because of small estimation fluctuations.

7. Integrated Applied Case: Real-Time API Reliability

Background

Consider an illustrative cloud service receiving millions of API calls per minute. Engineers need a bounded-memory dashboard showing request volume, distinct users, p99 latency, and dominant error codes across regions.

Problem

Storing every user identifier, latency, and error event is expensive and creates privacy exposure. Exact global aggregation also introduces network traffic and coordination delay.

Approach

Each regional collector maintains:

• a CMS for endpoint and error-code frequencies;
• an HLL for distinct active users;
• a KLL or t-digest for latency quantiles;
• a Space-Saving table for candidate top endpoints;
• a reservoir sample for forensic inspection of representative requests, with sensitive fields removed or tokenized.

Collectors use common hash seeds and compatible parameters. At fixed intervals, CMS tables are added, HLL registers are maximized, and quantile sketches are merged using the implementation’s merge operation. Candidate endpoint identifiers are sent with estimates for global verification.

Analysis and outcome

Suppose the service processes N = 10,000,000 requests in an interval and CMS is configured with ε = 0.0005. Its additive error allowance is approximately 5,000 requests for a fixed query at the stated confidence. This may be adequate for identifying endpoints with millions of calls, but not for distinguishing two endpoints whose counts differ by 1,000. The engineering team therefore uses CMS for coarse alerting and exact counters for a small, business-critical endpoint allowlist.

HLL supplies a compact estimate of unique users, while the latency sketch supplies a distributional view rather than an average. The reservoir supports debugging but is explicitly labeled a sample, not a complete incident record.

Learning points

The system succeeds because each structure is matched to a query type. It also exposes an important governance principle: approximate analytics should state uncertainty in dashboards and should not silently become the sole basis for punitive action, billing disputes, or user-level decisions.

8. Engineering, Governance, and Limitations

Accuracy and validation

Test sketches against exact computations on sampled or replayed streams. Measure bias, tail behavior, merge error, and sensitivity to skew. Use independent random seeds in tests, but preserve reproducible seeds for controlled experiments. Report confidence and parameter settings with every metric.

Windows and decay

Many structures summarize all history, whereas operators usually need the last five minutes or the current day. Windowing can be implemented with time buckets and periodic expiration, but naïvely subtracting sketches is not always valid. CMS with deletions needs signed updates and a different error analysis; HLL does not support simple subtraction. A ring of independently maintained bucket sketches is often safer, at the cost of additional memory.

Concurrency and distribution

Atomic increments, striping, thread-local sketches, and periodic merges offer different performance and consistency trade-offs. Distributed aggregation requires synchronized schemas, hash functions, and parameters. Late events and retries can cause double counting unless event identity or idempotent processing is available.

Privacy and security

A sketch may conceal individual records, but it is not automatically private. Repeated queries, small populations, and auxiliary information can enable inference. Hashing an identifier is pseudonymization rather than guaranteed anonymization. Sensitive applications may require access controls, minimum cohort sizes, noise addition, retention limits, and formal differential-privacy mechanisms. Randomized sketches can also be attacked through adversarial inputs, hash flooding, or query selection.

Best-practice checklist

1. Define the query and error metric before choosing a structure.
2. State whether error is additive, relative, rank-based, or empirical.
3. Specify confidence, stream scope, window, and merge semantics.
4. Use independent, well-seeded hashes and protect against adversarial keys.
5. Size counters for worst-case volume and prevent overflow.
6. Validate against exact baselines and monitor drift.
7. Keep critical decisions outside the uncertainty margin.
8. Preserve a privacy-conscious sample only when its purpose is justified.
9. Version sketch parameters so historical metrics remain interpretable.

9. Contemporary Directions

Streaming systems increasingly combine sketches with columnar engines, edge processors, and online machine-learning pipelines. Learned summaries may exploit predictable distributions, but they require safeguards when data drift invalidates the learned model. Hardware acceleration and vectorized hashing reduce update cost, while mergeable summaries support federated and geographically distributed analytics.

Research continues on adversarially robust sketches, differential privacy, compressed quantile summaries, dynamic graph streams, and adaptive structures whose memory follows workload importance. The fundamental challenge remains unchanged: an approximate answer is useful only when its error, assumptions, and operational consequences are understood.

Chapter Summary

Streaming data structures summarize high-volume, potentially unbounded streams using bounded memory. Reservoir sampling produces a uniform sample of unknown-length streams. Count-Min Sketch estimates frequencies with one-sided additive error under insertion-only assumptions; its width and depth control error and failure probability. HyperLogLog estimates distinct cardinality using hashed register maxima and offers compact, mergeable summaries with relative error approximately proportional to 1/√m. Quantile sketches summarize distributional rank, but rank error and value error must not be confused. Heavy-hitter methods combine candidate maintenance with frequency estimation to identify dominant keys. In production, parameter choice, window semantics, mergeability, hash quality, validation, privacy, and uncertainty-aware decision-making are as important as the core algorithms.

Key Terms

Streaming algorithm: An algorithm that processes data items as they arrive, usually with limited memory.

Sketch: A compact probabilistic or deterministic summary supporting approximate queries.

Reservoir sampling: One-pass uniform sampling from a stream of unknown final length.

Count-Min Sketch: A hashed counter array for estimating nonnegative item frequencies.

Additive error: An error bounded by a quantity such as εN.

Failure probability: The probability that a stated approximation guarantee does not hold.

Hash collision: The mapping of different keys to the same counter or register location.

Cardinality: The number of distinct elements in a collection.

HyperLogLog: A register-based sketch for approximate distinct counting.

Relative standard error: Standard deviation divided by the quantity being estimated.

Quantile: A value associated with a specified cumulative rank in a distribution.

Rank error: Difference between the true and reported rank of a quantile estimate.

KLL sketch: A randomized compact sketch for approximate quantiles.

t-digest: A centroid-based quantile summary emphasizing distribution tails.

DDSketch: A logarithmic-binning sketch designed for relative value accuracy.

Heavy hitter: A key whose frequency constitutes a substantial fraction of stream volume.

Mergeability: The ability to combine summaries while preserving their intended semantics.

Sliding window: A bounded recent portion of a stream used for a query.

Differential privacy: A formal privacy framework that limits the effect of one individual’s data on outputs.

Review Questions

Short Answer Questions

1. Why does storing the first k stream items fail to produce a uniform sample?
2. What are the roles of width and depth in Count-Min Sketch?
3. Distinguish cardinality estimation from frequency estimation.
4. What is rank error in a quantile sketch?
5. Why is mergeability important in distributed streaming systems?

Long Answer Questions

1. Explain reservoir sampling Algorithm R and justify its uniformity invariant.
2. Derive the practical parameter relationship between CMS error, confidence, width, and depth.
3. Describe HyperLogLog’s hashing and register procedure, including small-range correction.
4. Compare GK, KLL, t-digest, and DDSketch for an observability platform.
5. Discuss the design of a privacy-conscious streaming analytics architecture.

Analytical / Application Questions

1. A stream contains 20 million events. Design a CMS configuration for additive error at most 0.1% of stream volume and failure probability at most 0.5%. State the resulting width, depth, and approximate memory using four-byte counters.
2. An organization needs the number of distinct users, p99 latency, and the top ten error codes from distributed regional streams. Select structures, explain merge operations, and identify one limitation for each choice.
3. A dashboard reports an estimated frequency of 52,000 for a key in a stream of 10 million events using a CMS with ε = 0.001. Explain the strongest valid interpretation of the estimate and whether it is sufficient to distinguish the key from another estimated at 51,500.

Multiple Choice Questions with Answers

Question 1

What property does standard reservoir sampling guarantee after processing n items with a reservoir of size k?

A. The first k items are retained permanently

B. Each item has probability k/n of being retained

C. Later items are always preferred

D. Every item is retained with probability 1/k

Correct Answer: B. Each item has probability k/n of being retained

Question 2

For an insertion-only Count-Min Sketch, why is the estimate not below the true frequency?

A. The minimum operation removes all collisions

B. Hash functions are collision-free

C. Collisions add nonnegative counts to counters

D. The sketch stores every key exactly

Correct Answer: C. Collisions add nonnegative counts to counters

Question 3

If ε = 0.001 and N = 1,000,000, what additive error allowance follows from the standard CMS bound?

A. 10

B. 100

C. 1,000

D. 10,000

Correct Answer: C. 1,000

Question 4

Which operation merges two compatible HyperLogLog sketches for union cardinality estimation?

A. Adding corresponding registers

B. Taking the maximum of corresponding registers

C. Averaging all registers

D. Taking the minimum of corresponding registers

Correct Answer: B. Taking the maximum of corresponding registers

Question 5

The approximate relative standard error of HyperLogLog is proportional to which quantity?

A. m

B. 1/m

C. √m

D. 1/√m

Correct Answer: D. 1/√m

Question 6

What does a rank-error guarantee for a quantile sketch primarily constrain?

A. The number of bytes per input value

B. The difference between true and estimated cumulative position

C. The maximum numerical distance between values

D. The number of distinct keys

Correct Answer: B. The difference between true and estimated cumulative position

Question 7

Which sketch is specifically designed to provide relative value accuracy through logarithmic binning?

A. DDSketch

B. Misra–Gries

C. HyperLogLog

D. Reservoir sampling

Correct Answer: A. DDSketch

Question 8

Why is a candidate-maintenance mechanism often combined with CMS for heavy hitters?

A. CMS cannot update counters

B. CMS alone does not identify which keys in a huge universe to query

C. CMS estimates only quantiles

D. CMS requires storing the complete stream

Correct Answer: B. CMS alone does not identify which keys in a huge universe to query

Question 9

With CMS width w = ⌈e/ε⌉ and ε = 0.01, what is the approximate width?

A. 28

B. 100

C. 272

D. 2,718

Correct Answer: C. 272

Question 10

Which statement about averaging independently computed quantiles is correct?

A. It is always equivalent to merging the underlying data

B. It is generally invalid for obtaining the global quantile

C. It is required for HyperLogLog

D. It eliminates all rank error

Correct Answer: B. It is generally invalid for obtaining the global quantile