Introduction

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.

Try It: One-Pass 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.

<!-- Streaming graph sketch demo: one-pass connectivity over insertions and deletions -->
<p class="hint">Edges arrive one at a time — some are inserted (+), one is deleted (−). Click <b>Next edge</b> to process each event. The sketch tracks which nodes share a component, shown by color. No full edge list is stored.</p>
<div class="stream-header">
  <span class="stream-label">Edge stream</span>
  <span class="edge-counter" id="edge-counter">0 / 7 events</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">Press "Next edge" to start the stream.</div>
<div class="btns">
  <button id="btn-next" type="button">Next edge</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Visual styles for the streaming graph sketch demo */
* { 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; }

// Streaming graph sketch: union-find connectivity over a dynamic edge stream
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

// Fixed set of vertices in the graph
const NODES = ['A','B','C','D','E','F'];
const N = NODES.length;

// The edge stream: a sequence of insertion and deletion events
// Deletions are valid only for currently live edges
const STREAM = [
  { type: 'insert', u: 'A', v: 'B' },
  { type: 'insert', u: 'C', v: 'D' },
  { type: 'insert', u: 'B', v: 'C' },
  { type: 'insert', u: 'E', v: 'F' },
  { type: 'delete', u: 'B', v: 'C' },
  { type: 'insert', u: 'D', v: 'E' },
  { type: 'insert', u: 'A', v: 'F' },
];

// One distinct color per connected component
const COMP_COLORS = ['#3a7bd5','#e63946','#2a9d8f','#e9c46a','#f4a261','#9b5de5'];

// Union-find (disjoint-set) structure — the core of the insertion-only sketch
function makeUF() {
  const parent = {}, rank = {};
  for (const n of NODES) { parent[n] = n; rank[n] = 0; }
  return {
    find(x) {
      // Path-halving find
      while (parent[x] !== x) { parent[x] = parent[parent[x]]; x = parent[x]; }
      return x;
    },
    union(a, b) {
      // Union by rank
      const ra = this.find(a), rb = this.find(b);
      if (ra === rb) return false;
      if (rank[ra] < rank[rb]) parent[ra] = rb;
      else if (rank[ra] > rank[rb]) parent[rb] = ra;
      else { parent[rb] = ra; rank[ra]++; }
      return true;
    },
    components() {
      // Collect all components as lists of node names
      const map = {};
      for (const n of NODES) {
        const r = this.find(n);
        if (!map[r]) map[r] = [];
        map[r].push(n);
      }
      return Object.values(map);
    }
  };
}

// Fixed pixel positions for each node on the 340x160 canvas
const POS = {
  A: [50, 80], B: [120, 40], C: [190, 80],
  D: [190, 130], E: [265, 55], F: [265, 130]
};

// Global state: union-find, stream step index, live edges
let uf = makeUF();
let step = 0;
// The set of edges currently in the graph
let liveEdges = [];

function getNodeColor(node) {
  // Map each node to its component's color
  const comps = uf.components();
  for (let i = 0; i < comps.length; i++) {
    if (comps[i].includes(node)) return COMP_COLORS[i % COMP_COLORS.length];
  }
  return '#888';
}

function draw() {
  const canvas = document.getElementById('graph-canvas');
  const ctx = canvas.getContext('2d');
  ctx.clearRect(0, 0, canvas.width, canvas.height);

  // Draw live edges first (behind nodes)
  ctx.lineWidth = 2;
  ctx.strokeStyle = '#aaa';
  for (const { u, v } of liveEdges) {
    const [x1, y1] = POS[u], [x2, y2] = POS[v];
    ctx.beginPath(); ctx.moveTo(x1, y1); ctx.lineTo(x2, y2); ctx.stroke();
  }

  // Draw each node as a colored circle with its label
  for (const node of NODES) {
    const [x, y] = POS[node];
    const color = getNodeColor(node);
    ctx.beginPath(); ctx.arc(x, y, 16, 0, 2 * Math.PI);
    ctx.fillStyle = color; ctx.fill();
    ctx.strokeStyle = '#fff'; ctx.lineWidth = 2; ctx.stroke();
    ctx.fillStyle = '#fff'; ctx.font = 'bold 13px system-ui, sans-serif';
    ctx.textAlign = 'center'; ctx.textBaseline = 'middle';
    ctx.fillText(node, x, y);
  }
}

function renderPills() {
  // Render the stream as pills; highlight the most recently processed event
  const el = document.getElementById('event-list');
  el.innerHTML = '';
  STREAM.forEach((ev, i) => {
    const pill = document.createElement('span');
    const sign = ev.type === 'insert' ? '+' : '-';
    pill.className = 'event-pill ' + ev.type + (i === step - 1 ? ' active' : '');
    pill.textContent = sign + ev.u + '–' + ev.v;
    el.appendChild(pill);
  });
}

function setStatus(text, cls) {
  const el = document.getElementById('status');
  el.textContent = text; el.className = 'status ' + cls;
}

function updateCounter() {
  document.getElementById('edge-counter').textContent =
    i18nFmt('%n% / %total% events', { n: step, total: STREAM.length });
}

function applyStep() {
  if (step >= STREAM.length) return;
  const ev = STREAM[step];
  step++;

  if (ev.type === 'insert') {
    // Record the new edge and merge the two components
    liveEdges.push({ u: ev.u, v: ev.v });
    uf.union(ev.u, ev.v);
    const comps = uf.components();
    setStatus(
      i18nFmt('Inserted %u%–%v%. Graph has %k% component(s).', { u: ev.u, v: ev.v, k: comps.length }),
      'ok'
    );
  } else {
    // Remove the deleted edge from the live set, then rebuild union-find from scratch
    liveEdges = liveEdges.filter(e => !(e.u === ev.u && e.v === ev.v) && !(e.u === ev.v && e.v === ev.u));
    // Full rebuild simulates the recovery step of a linear sketch after a deletion
    uf = makeUF();
    for (const e of liveEdges) uf.union(e.u, e.v);
    const comps = uf.components();
    setStatus(
      i18nFmt('Deleted %u%–%v%. Sketch rebuilt: %k% component(s).', { u: ev.u, v: ev.v, k: comps.length }),
      'warn'
    );
  }

  if (step >= STREAM.length) {
    document.getElementById('btn-next').disabled = true;
    const comps = uf.components();
    setStatus(i18nFmt('Stream finished. Final graph: %k% connected component(s).', { k: comps.length }), 'info');
  }

  renderPills();
  updateCounter();
  draw();
}

function reset() {
  // Reset all state to the initial empty graph
  uf = makeUF();
  step = 0;
  liveEdges = [];
  document.getElementById('btn-next').disabled = false;
  renderPills();
  updateCounter();
  draw();
  setStatus('Press "Next edge" to start the stream.', '');
}

document.getElementById('btn-next').addEventListener('click', applyStep);
document.getElementById('btn-reset').addEventListener('click', reset);

// Initialize the demo on page load
reset();
Result
Console

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 ℓ0\ell_0 sampling) still handles the fully dynamic case in O(nlog⁡2n)O(n \log^2 n) bits — far less than the O(n2)O(n^2) needed to store all edges explicitly.

The Real Complexity

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

  • The semi-streaming model allows O(npolylog⁡n)O(n \operatorname{polylog} n) bits of working memory, where nn is the number of vertices. This is far less than the Θ(n2)\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)(u, v) a random ±1\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(nlog⁡3n)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 Ω(n)\Omega(n) bits. The gap between Ω(n)\Omega(n) and O(npolylog⁡n)O(n \operatorname{polylog} n) is essentially closed by these sketches.
  • Multiple passes: if you are allowed kk passes, you can solve problems like kk-connectivity and find minimum spanning forests, using O(npolylog⁡n)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.

Where It Matters

"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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/streaming-graph-sketches/Content licensed under CC BY-NC 4.0.