Streaming Graph Sketches

Imagine a router logging every packet it forwards, or a social platform recording every new follow. The edges of these massive graphs arrive in a continuous stream — too fast and too numerous to store in full. Yet you still need to answer questions: are these two users connected? How many components does the network have?

The classic approach of building and querying an adjacency matrix is hopeless when a graph has billions of edges and you have only megabytes of RAM. Streaming graph sketches offer a different deal: read each edge exactly once, maintain a tiny summary in memory, and at the end extract a complete answer.

The key insight, developed through a series of breakthroughs from the late 1990s through the 2010s, is that linear algebra can do what direct storage cannot. A linear sketch is a small random projection of the edge set; it supports updates (both insertions and deletions) by simple addition and subtraction, and it compresses exponentially without losing the information needed for connectivity.

Each row below is one edge event in the stream. Click Next edge to feed edges one at a time into a union-find structure. The sketch merges components as insertions arrive and splits them when a deletion removes the last bridge. Watch the connected components update with each step.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="stream-header">
  <span class="stream-label">{{label_stream}}</span>
  <span class="edge-counter" id="edge-counter">{{label_edge_0}}</span>
</div>
<div id="event-list" class="event-list"></div>
<div id="canvas-wrap" class="canvas-wrap">
  <canvas id="graph-canvas" width="340" height="160"></canvas>
</div>
<div class="status" id="status">{{status_ready}}</div>
<div class="btns">
  <button id="btn-next" type="button">{{btn_next}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.stream-header { display: flex; align-items: baseline; gap: .5rem; margin-bottom: .3rem; }
.stream-label { font-size: .75rem; font-weight: 700; text-transform: uppercase;
                letter-spacing: .06em; color: #5a7088; }
.edge-counter { font-size: .75rem; color: #888; }
.event-list { display: flex; flex-wrap: wrap; gap: 4px; margin-bottom: .5rem; min-height: 28px; }
.event-pill { font-size: .78rem; font-family: ui-monospace, monospace;
              padding: 2px 7px; border-radius: 12px; border: 1px solid #cdd9e3;
              background: #e8eef3; color: #1d3557; transition: background .2s; }
.event-pill.insert { background: #d4edda; border-color: #8fc9a0; color: #155724; }
.event-pill.delete { background: #fde8e8; border-color: #e6a0a0; color: #721c24; }
.event-pill.active { outline: 2px solid #1d3557; outline-offset: 1px; }
.canvas-wrap { background: #f5f7fa; border: 1px solid #cdd9e3; border-radius: 8px;
               margin-bottom: .5rem; overflow: hidden; }
canvas { display: block; width: 100%; }
.status { font-size: .95rem; font-weight: 600; margin: .3rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.status.warn { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .42rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: not-allowed; }

// Code not found

Notice that the sketch never stores the full edge list — it only tracks which nodes are in the same component. When deletions arrive the sketch must work harder, but a proper linear sketch (based on random $\ell_0$ sampling) still handles the fully dynamic case in $O(n \log^2 n)$ bits — far less than the $O(n^2)$ needed to store all edges explicitly.

How tight are these space bounds, and what exactly can one pass achieve?

• The semi-streaming model allows $O(n \operatorname{polylog} n)$ bits of working memory, where $n$ is the number of vertices. This is far less than the $\Theta(n^2)$ bits needed to store the whole graph, yet enough to maintain a spanning forest.
• Insertion-only streams: a simple union-find structure processes each edge in nearly constant time and decides connectivity perfectly. This has been known since the 1990s.
• Insertion–deletion (turnstile) streams: here the breakthrough came from Ahn, Guha, and McGregor (2012). They showed that assigning each edge $(u, v)$ a random $\pm 1$ weight and summing these weights into a small sketch vector per vertex preserves enough information to recover a spanning forest at query time, even when edges are deleted. Their algorithm uses $O(n \log^3 n)$ bits — exponentially less than full storage.
• Lower bounds: information-theoretic arguments prove that any single-pass algorithm for connectivity needs $\Omega(n)$ bits. The gap between $\Omega(n)$ and $O(n \operatorname{polylog} n)$ is essentially closed by these sketches.
• Multiple passes: if you are allowed $k$ passes, you can solve problems like $k$-connectivity and find minimum spanning forests, using $O(n \operatorname{polylog} n)$ space per pass.

The result is surprising: connectivity — a property that seems to require knowing the whole graph — can be determined by a sketch that is only logarithmically larger than the vertex count. This is the power of randomized algorithms applied to the streaming setting.

"Process a massive graph in one pass with tiny memory" is not a theoretical curiosity — it is an engineering necessity in many domains:

• Network monitoring: internet routers observe billions of flow records per day. Sketches answer reachability and anomaly questions without storing the full traffic graph.
• Distributed graph processing: frameworks like Pregel and GraphX partition graphs across machines. Sketches let each machine summarize its local edge set; the coordinator merges summaries in logarithmic space.
• Database query optimization: cardinality estimators for graph-shaped queries (join orders, path queries) use sketch techniques to estimate result sizes without materializing intermediate graphs.
• Social network analysis: detecting communities, finding bridges, and measuring connectivity in networks of hundreds of millions of users requires exactly the sub-linear memory that sketches provide.
• Sensor and IoT networks: sensors transmit edge events over constrained links; a sketch compressed at the source can answer global topology questions at the sink.

Streaming graph sketches sit at the intersection of randomized algorithms and data structures — a reminder that the right mathematical lens can make an apparently impossible problem tractable.

Streaming graph sketches reveal a beautiful truth: connectivity is a linear property. Even as edges pour in and out of a massive graph, a small random projection of the edge set — updated by addition and subtraction alone — carries enough information to reconstruct the spanning structure at the end of the stream.

The result of Ahn, Guha, and McGregor closed a long-open question and opened a new chapter in the study of sub-linear algorithms. The next time you wonder how a social platform can tell you "these two people are connected" without materializing a billion-edge graph, the answer lives in a tiny sketch — a handful of numbers that compress an entire network's topology into something that fits in your pocket.