When dealing with massive real-world networks—such as social graphs, web crawls, or financial transaction logs—the sheer volume of data breaks traditional algorithmic assumptions. In standard graph theory, we assume random access to the entire graph structure. However, when a graph contains billions of vertices ($n$) and trillions of edges ($m$), it cannot fit into a single machine's random-access memory.
To tackle this, researchers use the streaming model, where the graph is presented as a sequential stream of edges. The most practical variant of this framework is the semi-streaming model. In this model, the algorithm's memory is strictly constrained to $O(n \text{ polylog } n)$ space. This means we have enough memory to store a few pieces of information per vertex, but we cannot afford to store the edges.
The fundamental challenge of semi-streaming graph processing is a structural one: how do you compute global properties of a network when you are forced to discard almost all of its connections as they fly past?
The Core Tension: Local Decisions vs. Global Context
Consider the problem of finding a Maximum Matching—the largest possible set of edges that do not share any vertices. In a standard offline setting, a simple greedy algorithm yields a 2-approximation. But in a single-pass stream, edges arrive one by one. If we accept an edge into our matching, we commit its endpoints. If better edges arrive later, we might regret our choice, but the discarded edges are gone forever.
As Michael Kapralov demonstrates in Space Lower Bounds for Approximating Maximum Matching in the Edge Arrival Model, this restriction forces a severe trade-off between memory efficiency and approximation accuracy. Because the semi-streaming space cannot capture the global structure, algorithms must find clever ways to compress the graph on the fly without losing critical topological information.
For some problems, the constraints are even more brutal. In An optimal space lower bound for approximating MAX-CUT, Dmitry Krachun proved that beating a trivial 2-approximation for the MAX-CUT problem is mathematically impossible unless you use memory proportional to the number of vertices, showing that sublinear space fundamentally limits our ability to optimize global cuts.
Overcoming Adversaries via Random Ordering
One of the most powerful levers for breaking through these theoretical limits is changing the assumption about how data arrives. In an adversarial stream, an opponent orders the edges to exploit the algorithm's blind spots. In a random-order stream, the edges arrive in a uniformly random permutation.
Random arrival allows algorithms to treat the early part of the stream as a statistical sample of the entire graph. In Approximating matching size from random streams, Madhu Sudan et al. leveraged this property to approximate the size of a maximum matching using only polylogarithmic space in a single pass.
Building on this intuition, Sepehr Assadi broke a long-standing theoretical barrier in Beating Two-Thirds For Random-Order Streaming Matching. By maintaining an Edge-Degree Constrained Subgraph (EDCS)—a sparse skeleton of the graph that preserves matching properties—and combining it with a novel online augmentation strategy, the author proved that random-order streams allow us to surpass the traditional $2/3$ approximation barrier that stymies adversarial streams.
Multi-Pass Sketches and Optimization Hierarchies
When a single pass over an adversarial stream is insufficient, allowing the algorithm to make a small number of passes over the data can unlock near-optimal solutions. The strategy here shifts from simple greedy collection to iterative refinement via sketches and hierarchies.
For instance, in All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method, Sepehr Assadi et al. combined the Multiplicative Weights Update (MWU) method with a "matching hierarchy" structure. By reviewing the edge stream $O(\log n)$ times, the algorithm dynamically adjusts fractional weights on vertices, allowing it to find a globally balanced resource allocation that is simultaneously near-optimal for every $\ell_p$-norm while strictly adhering to semi-streaming memory limits.
However, adding passes is not a silver bullet. There is a fundamental tension between the number of passes and the memory footprint. In Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams, Sepehr Assadi et al. proved that for dynamic streams (where edges can be both inserted and deleted), exactly $\Theta(\log \log n)$ passes are required to approximate maximum matchings under semi-streaming constraints.
The Output Size Bottleneck
A unique paradox arises in problems like Edge Coloring, where the goal is to assign colors to edges such that no two adjacent edges share a color. Here, the size of the output itself is $O(m)$, which exceeds the semi-streaming memory budget of $O(n)$. How can an algorithm output a solution that it cannot even hold in memory?
To resolve this, researchers utilize the W-streaming model, where the output is streamed out sequentially alongside the input passes. As Soheil Behnezhad et al. point out in Brief Announcement: Streaming and Massively Parallel Algorithms for Edge Coloring, standard greedy coloring fails because the algorithm cannot remember past coloring decisions to ensure future consistency.
To bypass this, single-author works like Streaming Edge Coloring with Asymptotically Optimal Colors by Mohammad Saneian reduce the problem to finding matchings within an auxiliary "color graph." This allows the algorithm to achieve an asymptotically optimal $O(\Delta)$ coloring using sublinear space by processing edges in structured batches.
By shifting the focus from storing the entire graph to maintaining dynamic, vertex-proportional summaries, semi-streaming algorithms successfully bridge the gap between strict hardware limitations and the global demands of complex graph topologies.