12. Online, Streaming and Large-Scale Data Algorithms

Introduction and Context

Classical algorithm design usually assumes that the complete input is available before computation begins. An algorithm can inspect data repeatedly, sort it, store intermediate results, and revise decisions after seeing future items. Many contemporary systems violate these assumptions. A fraud-detection service must decide whether to approve a transaction before the next transaction arrives; a recommendation platform must process millions of events per second; and a cloud analytics system may receive data whose volume exceeds the capacity of one machine.

This chapter studies algorithms designed for such environments. Online algorithms process requests sequentially and make decisions without knowing future requests. Streaming algorithms process high-volume data using very small memory, often making only one or a few passes over the input. Large-scale data algorithms address data distributed across machines or stored in external memory, where communication and input/output operations may dominate arithmetic computation.

The central design challenge is therefore not merely computational efficiency. It is the management of uncertainty, memory, communication, latency, accuracy, and failure. Exact answers may be too expensive, while approximate answers may be acceptable if their error is measured and controlled. A sound algorithmic design must make these trade-offs explicit.

Learning Objectives

After studying this chapter, students should be able to:

1. Distinguish online, streaming, distributed, and external-memory computation models.

2. Explain competitive analysis and compare online algorithms with offline optimal solutions.

3. Design and analyse sketches, sampling methods, and approximate frequency algorithms.

4. Select appropriate algorithms for latency, memory, accuracy, and scalability requirements.

5. Explain external-memory and distributed processing principles, including communication costs.

6. Evaluate practical, ethical, and governance issues in real-time large-scale analytics.

The Computational Models Behind Modern Data Processing

Online computation

In an online problem, requests arrive one at a time. The algorithm must respond to the current request before seeing future requests. It may retain information about earlier requests, but it cannot retract a decision merely because later information makes another decision preferable.

Examples include allocating virtual machines, assigning arriving jobs to servers, routing packets, managing a cache, and accepting or rejecting advertisements. The online restriction creates uncertainty: the algorithm is judged partly by how well it protects itself against an unfavourable future.

An offline algorithm, by contrast, receives the entire sequence in advance. Offline knowledge often permits globally optimal decisions. It is therefore a useful benchmark even when it cannot be implemented in practice.

Streaming computation

A data stream is a sequence of items, events, updates, or measurements. A streaming algorithm typically has the following characteristics:

• one pass or a small number of passes over the data;
• memory much smaller than the stream length;
• processing time close to constant or logarithmic per item; and
• an exact or probabilistic approximation to a desired query.

Streaming algorithms are particularly valuable when storing the raw stream is impossible or undesirable. They are used for network monitoring, sensor analytics, clickstream analysis, cybersecurity, financial transactions, and machine-learning feature generation.

A stream may be an insertion-only stream, in which items are added but never removed, or a turnstile stream, in which updates may increment or decrement quantities. The update model affects which sketches and guarantees are valid.

External-memory computation

When data does not fit in main memory, the cost of moving data between storage and memory becomes important. The external-memory or input/output model represents computation using two parameters:

• N, the total number of data items; and
• B, the number of items transferred in one block between disk and memory.

The objective is often to minimise the number of block transfers rather than the number of comparisons. Sequential scans are usually much cheaper than random access. External sorting, blocked tree structures, and batched operations are therefore preferred over algorithms designed solely for random-access memory.

Distributed computation

Large datasets are commonly partitioned among many machines. A distributed algorithm must account for local computation, network communication, synchronisation, data skew, fault tolerance, and stragglers. A computation that is efficient on one machine may become inefficient when intermediate data must be transferred repeatedly across a network.

The MapReduce pattern illustrates a general strategy. A map phase transforms records into key-value pairs; a shuffle phase groups values by key; and a reduce phase aggregates each group. Modern systems extend this model with in-memory dataflow, stream processing, approximate aggregation, and adaptive scheduling.

Online Decisions and Competitive Analysis

The quality of an online algorithm cannot normally be measured against the unknown future directly. Competitive analysis provides a principled alternative. Let ALG(I) be the cost incurred by an online algorithm on input sequence I, and OPT(I) be the cost of an optimal offline algorithm. ALG is c-competitive if, for every input I,

ALG(I) <= c OPT(I) + a,

where c is the competitive ratio and a is a constant independent of I. Smaller c is better for minimisation problems. The additive constant handles small instances and is usually less important for long sequences.

Competitive analysis is deliberately worst-case. It asks whether an adversary can construct a sequence that makes the online algorithm perform poorly. This provides strong guarantees, although it may be pessimistic when real workloads have regular patterns.

The ski-rental problem

A simple example illustrates the value of competitive reasoning. Suppose renting equipment costs one unit per day and purchasing it costs K units. The duration of use is unknown. An online strategy rents until it has paid approximately K, then buys. If the user stops just before the purchase point, the strategy pays nearly K while the offline optimum pays only the number of days used. If use continues for a long time, the online cost is at most about twice the optimum. Thus a threshold policy achieves a constant competitive ratio.

The example appears in cloud computing, subscription management, and energy procurement. The important idea is not the particular threshold, but the balancing of immediate expenditure against the risk of committing too early.

Paging and caching

In paging, a system has a cache of k pages. A request for a page already in the cache is a hit; otherwise a page fault occurs and some cached page must be evicted. The offline optimal algorithm evicts the page whose next request is farthest in the future, but this policy is impossible online.

The least recently used (LRU) policy evicts the page that has not been accessed for the longest time. LRU is not always optimal, but it performs well under locality of reference and has a useful competitive guarantee. The example demonstrates an important distinction: theoretical robustness and practical performance may depend on different assumptions. An algorithm can be competitive in the worst case yet inferior to a workload-specific heuristic, or vice versa.

Randomisation and advice

Randomised online algorithms use random choices to prevent an adversary from predicting every decision. Their performance is analysed through expected cost. Randomisation is useful in load balancing, caching, routing, and resource allocation, but randomness does not remove the need for monitoring and safety constraints.

Another approach is advice: an external source provides limited information about the future. In practical systems, predictions from a machine-learning model can be interpreted as imperfect advice. The algorithm should remain safe when predictions are wrong. This leads to robust predictive algorithms that use forecasts to improve average performance while retaining a worst-case fallback.

Streaming Algorithms: Exactness Under Severe Memory Constraints

A stream of n items may contain far more information than can be stored. The algorithm must preserve only the information relevant to future queries. This is a form of lossy compression guided by a query class.

Sampling

Uniform sampling selects a representative subset of stream items. If the stream length is known, a sample of size k can be selected by choosing each item with appropriate probability. When the length is unknown, reservoir sampling maintains k items so that every item seen so far has equal probability of being retained.

For reservoir sampling, the first k items fill the reservoir. At position i, where i>k, the algorithm selects the new item with probability k/i and, if selected, replaces a uniformly chosen reservoir item. This requires O(k) memory and one pass. It is useful for exploratory analysis, auditing, and training-data inspection.

Sampling estimates must include uncertainty. A sample proportion is not automatically reliable for rare events, and uniform sampling may miss precisely the cases that matter most, such as fraud or system failures. Stratified, weighted, or priority sampling may be preferable when populations are heterogeneous.

Frequency estimation

Suppose a stream contains identifiers and the system needs to estimate how often each identifier occurs. An exact dictionary may require memory proportional to the number of distinct identifiers. A Count-Min Sketch uses a small array of counters and several hash functions. Each incoming item increments one counter in every corresponding row. To estimate an item's frequency, the algorithm returns the minimum counter among its hashed positions.

Hash collisions can only increase the estimated frequency, so the Count-Min Sketch gives an upper-bound estimate. With suitable dimensions, the error is bounded with high probability. It is appropriate for heavy-hitter detection, traffic measurement, and approximate query processing. It is less suitable when exact counts or unbiased estimates are required.

The design illustrates a general sketching principle: map a large domain into a compact structure, tolerate controlled collisions, and derive a probabilistic error guarantee.

Distinct counting

Counting distinct users, devices, or queries exactly can require storing every identifier. Probabilistic cardinality estimators, such as HyperLogLog-style methods, instead record patterns in hashed values. The occurrence of unusually long runs of leading zero bits suggests a large number of distinct items. Multiple registers are combined to reduce variance.

The result is an estimate with small memory usage and a predictable relative error. Such algorithms are valuable when many groups must be monitored simultaneously. Their weakness is that hash quality, parameter selection, and error interpretation matter; an estimate should not be treated as an exact business fact.

Frequency moments and norm estimation

For frequency vector f, the second frequency moment is F2 = sum f_i^2. It measures concentration: a stream dominated by a few items has a larger F2 than a uniformly distributed stream. Random-projection sketches can estimate such quantities without storing the full vector. These methods support anomaly detection, similarity estimation, and query optimisation.

Windows, Decay, and Change Detection

Real-time applications often care more about recent activity than historical totals. A sliding-window query asks about the most recent W items or the most recent time interval. Maintaining an exact window can still be expensive, especially when events arrive at high speed.

Exponential decay assigns larger weights to recent events. If an observation arrives at time t, its contribution may be multiplied by an attenuation factor as time passes. Decay provides smooth adaptation but makes the meaning of a statistic dependent on the chosen half-life.

Windowed algorithms must define event time, processing time, and lateness. In distributed systems, events may arrive out of order. Watermarks and allowed lateness policies help determine when a window is considered sufficiently complete. Poor choices can cause either inaccurate results or excessive delay.

Change detection methods compare recent and historical distributions. A rise in error rates, a shift in feature values, or an unusual frequency pattern may indicate fraud, a software defect, or concept drift in a predictive model. Detection thresholds should account for multiple testing, seasonality, and expected operational variation.

Large-Scale Processing and Data Locality

Large-scale systems succeed when computation is moved close to data and data movement is reduced. Partitioning determines which machine processes each record. A good partition function balances load, preserves useful locality, and avoids excessive communication.

Joins illustrate the difficulty. A broadcast join sends a small relation to every worker and is efficient when one input is small. A hash-partitioned join sends matching keys to the same workers and is more suitable when both relations are large. A skewed key, such as a very popular account, can overload one worker even when total data is balanced. Salting, adaptive partitioning, and special treatment of heavy keys can reduce this problem.

Fault tolerance is commonly achieved through replication, checkpointing, recomputation, or idempotent processing. Exactly-once semantics are difficult in the presence of failures and external side effects. Systems often achieve effectively-once results through unique event identifiers, transactional sinks, and replay-safe operations.

A Practical Design Framework

An engineer choosing an algorithm should begin with the query and the operating constraints rather than with a favourite data structure. The following questions are useful:

1. Is the data finite, unbounded, or repeatedly updated?

2. Must decisions be made immediately, or is batch delay acceptable?

3. What memory, storage, and network budgets are available?

4. Is exactness required, or is a stated error bound acceptable?

5. Are updates insert-only, deletions allowed, or corrections expected?

6. What are the consequences of false positives and false negatives?

7. How will failure, late data, duplication, and adversarial inputs be handled?

A production design should specify not only the algorithm but also its error model, parameter choices, monitoring metrics, reset policy, and fallback behaviour. For example, a sketch may be combined with exact storage for high-value entities, while a sampling system may oversample rare but consequential events.

Illustrative Case Study: Real-Time Detection of Abnormal Payment Activity

Background

Consider a fictional digital payments platform processing a very large number of transactions. It wants to identify merchants and accounts whose activity suddenly becomes abnormal while keeping decision latency low.

Situation and problem

Exact storage of every transaction and exact frequency calculation would be expensive. Moreover, fraud patterns change over time. The platform needs estimates of transaction frequency, the number of distinct devices, and recent activity, while investigators require access to exact records for selected cases.

Analysis

A single algorithm cannot satisfy all requirements. Exact transaction records are needed for investigation and regulatory retention, but approximate summaries are better for fast global monitoring. The system must also handle duplicated messages, late events, and adversarial attempts to evade detection.

Approach

The platform uses a streaming pipeline with the following components:

• event identifiers and idempotent writes to prevent double counting;
• a Count-Min Sketch for approximate merchant and account frequencies;
• a cardinality sketch for distinct-device estimates;
• reservoir or priority samples for investigator inspection;
• sliding windows and exponential decay to emphasise recent behaviour;
• exact storage for transactions associated with triggered alerts; and
• periodic comparison of sketch estimates with exact samples to detect implementation errors.

A risk score combines velocity, device diversity, geographic inconsistency, and historical behaviour. The score does not automatically imply wrongdoing. High-risk cases are routed for additional verification, while low-confidence cases may receive step-up authentication rather than rejection.

Outcome

The design reduces memory and response time for broad monitoring while preserving exact evidence for selected investigations. Its effectiveness depends on careful calibration, monitoring of false alerts, and periodic review as customer behaviour changes.

Learning points

The case demonstrates layered approximation: compact summaries support rapid screening, while exact data is retained where the consequences justify its cost. It also shows that an algorithmic guarantee is not sufficient by itself. Operational policies, human review, data quality, and governance determine whether a streaming system is trustworthy.

Limitations, Risks, and Common Design Errors

Approximation can hide rare events, systematic bias, and severe local errors. A small average error does not guarantee acceptable error for every customer or subgroup. Hash-based methods may be attacked if their hash functions are predictable. Sampling may underrepresent minority populations or unusual failures. Randomised algorithms also require reproducibility controls when auditability is important.

Online algorithms can perform badly when workload assumptions change. A policy tuned for temporal locality may fail under adversarial or highly random access. Distributed systems introduce clock problems, duplicate events, partial failures, and inconsistent snapshots. External-memory algorithms can become inefficient when access patterns are random or when block sizes are poorly chosen.

Common mistakes include confusing an upper-bound estimate with an unbiased estimate, ignoring confidence intervals, treating a window statistic as a timeless fact, measuring only throughput while neglecting tail latency, and failing to test with skewed or adversarial data. Another error is allowing a predictive model to make irreversible decisions without a safe fallback.

Ethical, Governance, and Professional Considerations

Large-scale analytics often processes personal, behavioural, or location data. Data minimisation, purpose limitation, access control, retention limits, and secure deletion should be considered at design time. Where decisions affect credit, employment, access, safety, or law enforcement, approximation and automated scoring can create meaningful harm.

Systems should document data provenance, algorithm versions, error bounds, and known failure modes. Monitoring should examine performance across relevant groups rather than only aggregate accuracy. Human review must be meaningful, not merely a formal appeal mechanism. Privacy-preserving aggregation, pseudonymisation, differential privacy, and strict separation between operational and analytical data may reduce risk, although each introduces utility and implementation trade-offs.

Emerging Directions and Best Practices

Modern data platforms increasingly combine stream processing with machine learning. Learned indexes, predictive caching, adaptive sampling, and model-assisted query optimisation use predictions to improve resource allocation. The safest designs treat predictions as advice rather than truth and retain algorithmic safeguards when predictions fail.

Edge computing moves filtering and summarisation closer to sensors, reducing bandwidth and latency. Hardware accelerators and programmable network devices support high-speed sketches and packet analytics. Approximate query processing is also becoming more integrated with cloud data warehouses.

Best practice is to define service-level objectives for latency, freshness, accuracy, and availability; select algorithms with explicit probabilistic guarantees; test under realistic skew and failure; monitor drift and error; retain exact data only where justified; and design replay, correction, and audit mechanisms before deployment.

Chapter Summary

Online algorithms make sequential decisions without future knowledge and are evaluated through competitive analysis against offline optima. Streaming algorithms process massive or unbounded data using one or a few passes and limited memory. Sampling, Count-Min Sketches, cardinality estimators, frequency-moment methods, windows, and decay provide useful approximate analytics with explicit trade-offs.

External-memory and distributed algorithms focus on block transfers, locality, communication, partitioning, skew, and fault tolerance. Effective large-scale designs combine compact summaries for rapid global analysis with exact storage where decisions require evidence. Approximation, prediction, and automation must be accompanied by error measurement, robustness, privacy protection, fairness evaluation, and operational governance.

Key Terms

Online algorithm: An algorithm that processes requests sequentially without knowing future requests.

Offline algorithm: An algorithm that has access to the complete input in advance.

Competitive ratio: The worst-case ratio comparing an online algorithm with an optimal offline algorithm.

Adversary: A hypothetical or actual process that chooses inputs unfavourable to an algorithm.

Streaming algorithm: An algorithm that processes a data stream using limited memory and few passes.

Insertion-only stream: A stream containing additions but no deletions or negative updates.

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

Reservoir sampling: A one-pass method that maintains a uniform sample of an unknown-length stream.

Sketch: A compact probabilistic summary used to answer approximate queries.

Count-Min Sketch: A hashed counter structure that estimates frequencies with an upper-bound error.

Cardinality estimation: Estimation of the number of distinct elements in a dataset.

Frequency moment: A statistic such as the sum of powers of item frequencies.

Sliding window: A query restricted to the most recent items or time interval.

Exponential decay: A weighting method that gives progressively less importance to older data.

External-memory model: A model that measures computation largely by transfers between storage and memory.

Block transfer: Movement of a block of data between external storage and main memory.

Data locality: The principle of processing data near where it is stored.

Data skew: Uneven distribution of records or keys across processing workers.

Watermark: A system indicator of the progress of event-time processing.

Effectively-once processing: A practical guarantee achieved through replay-safe and idempotent operations.

Review Questions

Short Answer Questions

1. What distinguishes an online algorithm from an offline algorithm?

2. Why is competitive analysis useful for online decision problems?

3. State the main purpose of a Count-Min Sketch.

4. How does reservoir sampling maintain a uniform sample when stream length is unknown?

5. Why can data locality be more important than comparison count in external-memory computation?

Long Answer Questions

1. Explain the online, streaming, external-memory, and distributed computation models, comparing their principal resource constraints.

2. Describe competitive analysis using the ski-rental or paging problem as an illustration.

3. Explain how Count-Min Sketches and cardinality estimators reduce memory requirements, including their limitations.

4. Discuss the design issues involved in windowed stream processing with late and out-of-order events.

5. Analyse the role of partitioning, communication, skew, and fault tolerance in large-scale data processing.

Analytical / Application Questions

1. A monitoring system must estimate the number of distinct devices and identify heavy users from an unbounded stream. Propose an algorithmic design and justify its memory and accuracy trade-offs.

2. A cloud cache receives requests with strong temporal locality during normal operation but adversarial access patterns during attacks. Which online strategies and safeguards would you consider, and why?

3. Design a real-time transaction-monitoring pipeline that combines approximate screening with exact investigation records. Specify how you would address duplication, late data, privacy, false alerts, and model drift.

22. Multiple Choice Questions with Answers

Question 1

Which statement best characterises an online algorithm?

A. It receives the complete input before making any decision.

B. It makes decisions sequentially without knowing future requests.

C. It always produces an approximate answer.

D. It requires data to be stored on external memory.

Correct Answer: B. It makes decisions sequentially without knowing future requests.

Question 2

For a minimisation problem, an online algorithm is c-competitive when its cost is generally bounded by:

A. OPT(I) divided by c, with no additive term

B. c times the offline optimum plus a constant

C. The exact cost of the offline optimum

D. The stream length multiplied by c

Correct Answer: B. c times the offline optimum plus a constant

Question 3

What is a principal property of a Count-Min Sketch frequency estimate?

A. It is always less than the true frequency.

B. It is always exactly equal to the true frequency.

C. Hash collisions may cause it to overestimate the true frequency.

D. It requires storage for every distinct identifier.

Correct Answer: C. Hash collisions may cause it to overestimate the true frequency.

Question 4

Reservoir sampling is especially useful when:

A. The stream length is unknown and a uniform sample is required.

B. All stream items can be sorted before processing.

C. Every item must be stored exactly once.

D. Only deletion updates are permitted.

Correct Answer: A. The stream length is unknown and a uniform sample is required.

Question 5

In the external-memory model, algorithm designers primarily seek to reduce:

A. The number of arithmetic operations only

B. The number of block transfers between storage and memory

C. The number of variables in source code

D. The number of distinct keys in the input

Correct Answer: B. The number of block transfers between storage and memory

Question 6

Which operation is most likely to create a data-skew problem in a distributed join?

A. A uniformly distributed key being processed locally

B. A highly popular key sending many records to one worker

C. A small relation being broadcast to workers

D. A sequential scan over partitioned files

Correct Answer: B. A highly popular key sending many records to one worker

Question 7

Why are sliding windows used in stream analytics?

A. They give all historical events equal importance forever.

B. They restrict analysis to recent items or a recent time interval.

C. They eliminate the need to handle late events.

D. They guarantee exact results with constant memory.

Correct Answer: B. They restrict analysis to recent items or a recent time interval.

Question 8

Which design best combines fast approximate monitoring with reliable investigation?

A. Use only a sketch and discard all raw transactions.

B. Use exact storage for every possible derived statistic and no summaries.

C. Use compact summaries for screening and retain exact records for selected cases.

D. Use random decisions without logging their inputs.

Correct Answer: C. Use compact summaries for screening and retain exact records for selected cases.

Question 9

What is a major risk of interpreting a small average sketch error as a universal guarantee?

A. Every individual or subgroup is guaranteed to have small error.

B. Rare events or particular subgroups may experience substantially larger error.

C. The sketch becomes an exact database.

D. Network communication is eliminated.

Correct Answer: B. Rare events or particular subgroups may experience substantially larger error.

Question 10

In a streaming system with duplicated messages, which mechanism helps prevent double counting?

A. Idempotent processing based on unique event identifiers

B. Increasing the number of dashboard colours

C. Removing all timestamps

D. Using a larger batch without deduplication

Correct Answer: A. Idempotent processing based on unique event identifiers