Online, Streaming and Sublinear Algorithms

Introduction

Modern AI and information systems increasingly process data that is too fast, too large, or too continuously changing for conventional batch algorithms. Examples include clickstreams, sensor networks, financial transactions, network packets, social-media events, and model-inference logs. In such settings, an algorithm may see each item once, have only a bounded memory budget, and be required to produce decisions before the complete dataset exists.

This chapter studies algorithmic methods for these environments. The central design question is not simply whether an algorithm is correct, but what information must be retained, how much memory and communication it consumes, how quickly it responds, and how its output quality can be bounded. The principal paradigms are online algorithms, streaming algorithms, sublinear algorithms, sketches, sampling, sliding-window computation, external-memory processing, and memory-efficient analytics.

The methods are especially relevant to AI and ML systems. A recommender may update statistics continuously; a fraud detector may have milliseconds to react; and a data platform may estimate the frequency of billions of events without storing every event. Approximation is often not a weakness but the only feasible engineering choice. The essential requirement is to make approximation error, probability of failure, resource use, and operational assumptions explicit.

Learning Objectives

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

1. Distinguish online, streaming, sublinear, external-memory, and distributed computation models.
2. Apply competitive analysis to online decision problems.
3. Select sketches, sampling methods, and sliding-window techniques for large or evolving datasets.
4. Derive and interpret memory, time, communication, and error guarantees.
5. Design an approximate analytics pipeline with suitable validation and governance controls.
6. Evaluate limitations, adversarial risks, privacy implications, and deployment trade-offs.

1. Computational Models for Massive and Evolving Data

1.1 Online computation

An online algorithm receives a sequence of requests one at a time and must make an immediate or nearly immediate decision. Past decisions cannot normally be revised. The input sequence is often denoted a₁, a₂, ..., a_n, where the algorithm observes a_t before deciding its action at time t.

Online algorithms are judged against an offline optimum that knows the entire sequence in advance. If C_A(σ) is the cost incurred by algorithm A on sequence σ and C_OPT(σ) is the minimum cost achievable with complete knowledge, A is c-competitive when

for every admissible sequence σ, where c ≥ 1 is the competitive ratio and β is an additive constant independent of the input size. For maximization problems, the comparison is usually expressed as an algorithmic value at least a fraction of the offline optimum. Competitive analysis is worst-case and does not require a probability distribution over inputs.

1.2 Streaming computation

A streaming algorithm processes a long stream using memory much smaller than the stream length. In the strict turnstile model, updates have the form (i, Δ), changing frequency x_i to x_i + Δ; in the insertion-only model, Δ is nonnegative. A one-pass algorithm reads updates once, while a multi-pass algorithm may reread the stream a small number of times.

Important resource measures include:

A streaming algorithm commonly provides a probabilistic guarantee such as

where F is the exact quantity, F̂ is the estimate, B is a known scale or bound, ε is the accuracy parameter, and δ is the failure probability. The guarantee is meaningful only when the estimator, randomness, update model, and scale B are specified.

1.3 Sublinear algorithms

A sublinear algorithm uses less than linear time in the input size, or examines only a small portion of the input. Sampling algorithms are a common example. They are useful when accessing every record is itself expensive. Sublinear time may be measured in number of inspected records, oracle queries, or processed edges, rather than wall-clock time alone.

Sublinear algorithms require a query-access model. Uniform random access, adjacency-list access in a graph, and random sampling from a database are different assumptions. A claimed sublinear bound without a clear access model is incomplete.

1.4 External-memory and distributed models

When data exceeds main memory, an external-memory algorithm minimizes block transfers between storage and memory. Let N be the number of records, M the memory capacity, and B the number of records per I/O block. The standard I/O model measures transfers rather than individual arithmetic operations. Sorting and indexing are designed to exploit sequential access and locality.

Distributed streaming adds communication as a first-class cost. Multiple workers process partitions and exchange compact summaries. A method that is optimal in local memory may be poor if its summaries require excessive network traffic or if merging is not associative.

2. Competitive Analysis and Online Decisions

2.1 The ski-rental model

The ski-rental problem illustrates the tension between immediate and future costs. Renting costs r per day; buying costs b once, with b > r. The number of skiing days is unknown. A deterministic strategy rents for k days and then buys. If the trip lasts at least k days, its cost is kr + b; if it ends earlier, its cost is dr for d < k days.

Choosing k = ⌈b/r⌉ gives a competitive ratio below 2 in the standard integral-day formulation. Intuitively, the algorithm may pay nearly b in rent before buying, while the offline optimum either rents for a short trip or buys for a long one. Randomized strategies can improve the worst-case expected ratio when randomization is permitted.

The example generalizes to cloud provisioning, cache admission, equipment leasing, and model-serving capacity. A system should identify the unknown horizon, the irreversible action, and the cost of being early or late.

2.2 Paging and caching

In paging, a cache of k pages serves a request sequence. A hit costs zero; a miss requires loading a page and possibly evicting another. The least-recently-used (LRU) policy is k-competitive against the offline optimum under the standard paging model. This does not mean LRU is always best in practice: real workloads may contain scans, popularity skew, or predictive signals that violate the assumptions behind worst-case analysis.

Competitive analysis is valuable because it provides distribution-free protection, but it can be pessimistic. Average-case analysis, trace-driven evaluation, and learning-augmented algorithms can complement it. A learned predictor should not silently replace a worst-case safeguard; it should be monitored and bounded by a fallback policy.

3. Sketches for Approximate Stream Analytics

A sketch is a compact data structure supporting approximate queries over a stream. Good sketches have small memory, fast updates, mergeability, and explicit error guarantees.

3.1 Linear sketches and mergeability

A sketch is mergeable when the sketch of a union can be obtained by combining sketches computed independently. This property is essential in distributed systems. If S(D) is a sketch of dataset D and ⊕ is a valid merge operation, then

for the supported data model. Mergeability permits workers to process partitions independently and combine summaries without transmitting raw records.

3.2 Bloom filters

A Bloom filter represents set membership using an m-bit array and k hash functions. To insert an item, the k corresponding bits are set to one. A query returns “possibly present” if all those bits are one and “definitely absent” otherwise. It has no false negatives under correct operation, but it can have false positives.

For n inserted items and approximately independent uniform hashes, the false-positive probability is approximately

The approximation assumes a sufficiently large array and independent hashing. For fixed m and n, the approximate optimal number of hash functions is

Bloom filters do not support deletion safely unless enhanced variants, such as counting Bloom filters, are used. They are suitable for pre-filtering database lookups, duplicate suppression, and cache admission, but not for exact membership decisions.

3.3 Count–Min Sketch

The Count–Min Sketch estimates nonnegative frequencies. It uses d rows and w counters per row, with one hash function per row. On update (i, Δ), the counter selected in every row is incremented by Δ. To estimate the frequency of i, return the minimum counter among its d hashed positions.

For insertion-only streams and pairwise independent hashing, the estimate f̂_i satisfies, with probability at least 1 − δ,

when w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉; N is the total number of inserted items. The estimate is an upper bound because hash collisions only increase counters. The guarantee is additive, so it may be weak for very rare items when N is large. Conservative updates and heavy-hitter procedures can improve practical performance but alter the analysis.

3.4 HyperLogLog and distinct counting

Distinct-value estimation is often needed for users, devices, or products. HyperLogLog hashes each item, uses a prefix to select a register, and records a rank derived from the remaining hash bits. Its relative standard error is approximately

where m is the number of registers, under the usual hashing assumptions and in the well-calibrated range of the estimator. This is an approximate statistical relationship, not an exact guarantee for every cardinality. Bias correction and small- and large-range corrections are important in implementations.

4. Sampling and Randomized Estimation

Sampling reduces computation by retaining a representative subset. Uniform sampling is appropriate when every record should have equal inclusion probability. If records have unequal importance, stratified, weighted, or reservoir sampling may be preferable.

4.1 Reservoir sampling

To maintain a uniform sample of k items from an unknown-length insertion-only stream, store the first k items. For the t-th subsequent item, where t > k, retain it with probability k/t and, if retained, replace a uniformly selected stored item. After t items, every item has inclusion probability k/t.

The method requires O(k) memory and O(1) expected processing per item. It assumes that the stream is sampled sequentially and that the desired sample is uniform over positions. It does not automatically produce a uniform sample over bytes, users, or changing time windows.

4.2 Estimating a mean

For a finite population with values x₁, …, x_N, a uniform sample of k values without replacement provides the sample mean

as an unbiased estimator of the population mean μ under simple random sampling. If observations are independent with variance σ², the standard error of the mean is σ/√k. Without-replacement sampling from a finite population introduces the finite-population correction √((N − k)/(N − 1)). These formulas require suitable sampling and variance assumptions; dependence, clustering, and selection bias can invalidate naive confidence intervals.

For rare events, uniform sampling may miss all relevant records. Importance sampling or stratification should then allocate more sample mass to informative strata, while weighting observations to preserve unbiasedness.

5. Sliding Windows and Time-Evolving Statistics

A historical aggregate may be irrelevant when only recent behavior matters. A sliding window of width W at time t contains events with timestamps in (t − W, t]. The system must expire old events while incorporating new ones.

5.1 Exact windows

Exact counting is straightforward when events are stored in timestamp order: append new events and remove expired events. However, memory is proportional to the number of events in the window. For high-rate streams this may be unacceptable.

5.2 Approximate windows

Bucket-based methods group events into time intervals. Recent buckets are kept with greater resolution, while older buckets are merged. Exponential histograms are a classical approach for approximately counting ones in a binary stream. They maintain buckets whose sizes increase geometrically and retain only a bounded number of buckets of each size. The oldest partially represented bucket causes bounded error, with space logarithmic in the window length for fixed relative accuracy.

Time semantics must be explicit. Event time reflects when an event occurred; processing time reflects when it arrived. Late and out-of-order events require watermarks, lateness bounds, or correction mechanisms. A dashboard that silently mixes these semantics can report a plausible but incorrect trend.

6. External-Memory and Memory-Efficient Analytics

6.1 Block-aware design

External-memory algorithms should minimize random I/O. Sequential scans, blocked matrix operations, sort-merge joins, and compact columnar representations generally outperform record-at-a-time access. Compression can reduce I/O, but decompression cost and predicate selectivity must be considered.

For a relation of N records, a full scan costs approximately N/B block transfers, ignoring caching and metadata. A B-tree lookup is typically logarithmic in the number of blocks, but its practical cost depends on locality and concurrency. These are I/O-model estimates, not universal wall-clock predictions.

6.2 Approximate query processing

Approximate query processing may use samples, sketches, or synopsis tables to return estimates quickly. A production system should report confidence intervals or error bounds, identify stale summaries, and provide an escalation path to exact computation. Approximation is inappropriate when legal, safety-critical, or contractual requirements demand exact records.

6.3 Memory-efficient ML analytics

Feature pipelines can use streaming normalization, reservoir-based inspection, quantile sketches, and bounded-memory aggregations. Model training may use mini-batches, online gradient updates, or compressed sufficient statistics. A useful design separates:

1. raw-event retention policies;
2. approximate operational metrics;
3. exact audit and reconciliation data;
4. model-training data and labels.

A sketch should not be treated as an audit log. It generally cannot reconstruct individual records, explain every decision, or support arbitrary retrospective queries.

7. Worked Design Example: Streaming Heavy-Hitter Detection

Suppose a platform receives N = 10,000,000 product-view events and wants approximate frequencies for product IDs. It chooses a Count–Min Sketch with ε = 0.001 and δ = 0.01.

The required width and depth are

and

Thus the sketch contains 2719 × 5 = 13,595 counters. If each counter is a 64-bit integer, the counter storage is 13,595 × 8 = 108,760 bytes, approximately 106.2 KiB, excluding hash seeds and object overhead.

For any product i, the stated guarantee is, with probability at least 0.99,

This additive error is acceptable for detecting products viewed tens of thousands of times, but not for distinguishing products whose true counts differ by a few hundred. The system could reduce ε, use a two-stage candidate structure, or retain exact counts for a selected set of high-value products. The example demonstrates why a memory figure is never sufficient: the decision utility depends on the error scale relative to the business question.

8. Illustrative Case Study: Fraud Detection in a Payment Stream

Background

Consider a fictional payment platform processing millions of authorization events per hour. It must flag suspicious activity within seconds while limiting memory and network traffic across regional data centers.

Problem

Exact retention of all recent events is expensive. The platform needs recent distinct-device counts, merchant-level transaction frequencies, and rapid membership checks for known compromised identifiers. It must also avoid unfairly blocking legitimate customers and preserve an auditable basis for high-impact decisions.

Analysis

A single technique cannot satisfy all requirements. A Bloom filter can efficiently reject identifiers not in a compromised set, but its false positives require a second-stage verification. A Count–Min Sketch can estimate merchant and account frequencies, but collision error may inflate risk scores. Exact records are still needed for investigation and appeals. Sliding-window logic must distinguish event time from arrival time because delayed authorizations are common.

Approach and solution

The architecture uses a mergeable Count–Min Sketch per region for high-volume frequency features, HyperLogLog summaries for approximate distinct-device counts, and a versioned Bloom filter for rapid pre-filtering. A bounded event-time window retains exact records for a short investigation interval. Regional summaries are merged centrally. Risk rules use conservative thresholds and route borderline cases to a more expensive verifier rather than automatically declining them.

The monitoring layer measures false-positive and false-negative rates on labelled outcomes, sketch age, late-event rates, hash-seed versions, and regional merge consistency. Periodic exact samples estimate calibration error. Access to raw payment data is restricted, and retention is limited to the purpose and duration justified by policy.

Outcome

The design reduces memory and network traffic while preserving a path to exact review. Its principal benefit is not merely speed: it makes approximation explicit and confines irreversible actions to stages with stronger evidence.

Learning points

1. Use different summaries for different query types.
2. Treat probabilistic outputs as features or alerts, not unquestionable facts.
3. Preserve exact evidence for high-impact decisions.
4. Evaluate the system under distribution shift, adversarial input, and delayed data.
5. Version hash functions, parameters, schemas, and window definitions.

9. Limitations, Security, Ethics, and Governance

Approximate algorithms can fail systematically. Nonuniform sampling can underrepresent minority populations; sketches can be attacked through adversarial collisions or manipulated identifiers; and distribution drift can make historical thresholds obsolete. Random seeds and hash functions should be generated and managed appropriately, particularly where users can influence keys.

Privacy is not guaranteed merely because a summary is small. A sketch may leak information about membership or frequency, and repeated queries can enable inference. Differential privacy adds calibrated randomness to limit the effect of any one individual. In a basic counting query, a mechanism may release a perturbed count rather than the exact count; however, privacy loss accumulates across repeated releases and must be tracked with a formal accounting method.

Governance should specify:

• the data and update model;
• the approximation and confidence guarantee;
• acceptable error for each decision;
• retention and deletion behavior;
• treatment of late, corrected, or duplicated events;
• audit and reproducibility requirements;
• fallback behavior when summaries are unavailable or stale.

For regulated or safety-sensitive applications, approximate analytics should support—not replace—human review, documented controls, and legally required recordkeeping.

10. Contemporary Developments and Best Practices

Current systems increasingly combine streaming engines, vectorized execution, approximate query processing, edge analytics, and learned components. Learned indexes and learned admission policies can exploit workload regularities, but they should be evaluated against robust baselines and protected by fallback mechanisms. Sketches are also used in telemetry, federated aggregation, graph analytics, and large-scale feature stores.

Best practices include:

1. Start with the exact query and define the error that matters operationally.
2. State whether the stream is insertion-only, turnstile, ordered, or out of order.
3. Prefer mergeable summaries in distributed deployments.
4. Separate update-time, query-time, memory, communication, and I/O costs.
5. Test both average workloads and adversarial or worst-case inputs.
6. Validate estimates against periodic exact samples.
7. Monitor error, drift, staleness, and missing-event rates in production.
8. Keep raw evidence when decisions affect rights, safety, or money.
9. Document randomization, parameter choices, and version changes.
10. Use exact computation selectively for reconciliation and high-value exceptions.

Chapter Summary

Online algorithms make decisions without knowing future requests and are often evaluated through competitive analysis against an offline optimum. Streaming algorithms process massive sequences with bounded memory, while sublinear algorithms reduce the number of inspected records under an explicit access model. Sketches such as Bloom filters, Count–Min Sketches, and HyperLogLog provide compact approximate answers, each with a distinct query type and error behavior. Reservoir sampling supports uniform samples from unknown-length streams; stratified and importance sampling address unequal information value. Sliding-window methods preserve recency but require careful event-time semantics. External-memory algorithms optimize block transfers, and distributed methods must control communication through mergeable summaries. In AI and ML operations, these techniques enable scalable features and monitoring, but approximation must be accompanied by validation, privacy safeguards, auditability, and appropriate fallbacks.

Key Terms

Online algorithm: An algorithm that must act as input arrives without future knowledge.

Competitive ratio: Worst-case comparison between an online algorithm and an offline optimum.

Streaming algorithm: A bounded-memory algorithm that processes a sequential data stream.

Sublinear algorithm: An algorithm whose inspected input or running time is less than the full input size.

Insertion-only stream: A stream containing only nonnegative additions.

Turnstile model: A stream allowing positive and negative updates to item frequencies.

Sketch: A compact randomized summary supporting approximate queries.

Mergeability: The ability to combine summaries of partitions into a valid summary of their union.

Bloom filter: A compact probabilistic structure with no false negatives and possible false positives.

Count–Min Sketch: A frequency-estimation structure based on hashed counters and minimum queries.

Heavy hitter: An item whose frequency is large relative to the stream or a specified threshold.

HyperLogLog: A sketch for estimating the number of distinct values.

Reservoir sampling: Uniform sampling from a stream of unknown final length.

Sliding window: The recent interval of events retained for time-local analytics.

Event time: The time at which an event occurred.

Processing time: The time at which a system processed an event.

External-memory model: A model measuring transfers between main memory and storage.

Approximate query processing: Returning estimates instead of exact query results.

Differential privacy: A formal framework limiting the influence of one individual on released outputs.

Review Questions

Short Answer Questions

1. What distinguishes an online algorithm from a batch algorithm?
2. Why is mergeability important in distributed streaming?
3. What type of error can a Bloom filter produce?
4. State the purpose of reservoir sampling.
5. Why must event time and processing time be distinguished?

Long Answer Questions

1. Explain competitive analysis and discuss its strengths and limitations using caching as an example.
2. Describe the construction, query behavior, and error guarantee of a Count–Min Sketch.
3. Compare Bloom filters, HyperLogLog, and reservoir sampling in terms of their supported tasks.
4. Explain how sliding-window summaries manage high-rate streams and late events.
5. Discuss how external-memory and distributed constraints influence algorithm design.

Analytical / Application Questions

1. Design a bounded-memory architecture for estimating unique users and heavy products in a global clickstream. Justify the chosen summaries and validation strategy.
2. A fraud system uses a frequency sketch whose additive error is large relative to the rare events it must detect. Analyze at least three possible remedies and their trade-offs.
3. Develop a governance plan for an approximate algorithm used to influence financial decisions, including privacy, auditing, fallback, and error-monitoring requirements.

Multiple Choice Questions with Answers

Question 1

Which statement best describes a c-competitive online minimization algorithm?

A. It always uses exactly c memory words.

B. Its cost is at most c times the offline optimum, up to an additive constant.

C. It is correct only when inputs are uniformly random.

D. It always runs in sublinear time.

Correct Answer: B. Its cost is at most c times the offline optimum, up to an additive constant.

Question 2

What is a defining property of a Bloom filter under correct operation?

A. It has no false positives.

B. It supports exact deletion without modification.

C. It has no false negatives for inserted items.

D. It returns the exact frequency of every item.

Correct Answer: C. It has no false negatives for inserted items.

Question 3

For a Count–Min Sketch in an insertion-only stream, why is the minimum across rows used for an estimate?

A. To guarantee that hash collisions decrease the count.

B. To select the smallest collision-inflated counter.

C. To eliminate the need for hash functions.

D. To make all item frequencies equal.

Correct Answer: B. To select the smallest collision-inflated counter.

Question 4

If ε = 0.001 and a Count–Min Sketch processes N = 10,000,000 insertions, its stated additive error bound is

A. 10

B. 100

C. 1,000

D. 10,000

Correct Answer: D. 10,000

Question 5

What is the main purpose of reservoir sampling?

A. Maintaining a uniform sample from a stream of unknown length

B. Counting distinct values exactly

C. Removing all duplicate events

D. Sorting a stream externally

Correct Answer: A. Maintaining a uniform sample from a stream of unknown length

Question 6

Which operation is HyperLogLog primarily designed to estimate?

A. The number of distinct values

B. The shortest path in a graph

C. The exact median of a stream

D. The false-positive rate of a cache

Correct Answer: A. The number of distinct values

Question 7

In the external-memory model, the principal cost being optimized is usually

A. The number of source-code lines

B. The number of storage-to-memory block transfers

C. The number of distinct keys

D. The number of model parameters

Correct Answer: B. The number of storage-to-memory block transfers

Question 8

Why are mergeable sketches useful in distributed systems?

A. They require every raw record to be sent to a central server.

B. They allow partition summaries to be combined into a global summary.

C. They guarantee exact answers for every query.

D. They eliminate all network communication.

Correct Answer: B. They allow partition summaries to be combined into a global summary.

Question 9

A sliding event-time window contains events whose timestamps are typically

A. After t + W only

B. In the interval (t − W, t]

C. Before the system was installed

D. Equal to processing time in every case

Correct Answer: B. In the interval (t − W, t]

Question 10

Which governance practice is most appropriate when an approximate score influences a high-impact financial decision?

A. Discard all exact evidence to save memory.

B. Hide the approximation parameters from auditors.

C. Provide validation, audit records, and a stronger fallback or review path.

D. Assume that a small sketch is automatically private.

Correct Answer: C. Provide validation, audit records, and a stronger fallback or review path.