A natural approach to computing the connected components on a large, dynamic graph stream is to buy enough RAM to store the entire graph. Indeed, dynamic graph stream processing systems such as Aspen and Terrace [1]}, [2]} can efficently query the connected components of a large graph subject to a stream of edge insertions and deletions when the graph fits in RAM. However, the requirement that the graph fit in RAM is prohibitive for most large graphs: for example, a graph with ten million nodes and an average degree of 1 million, using 2B to encode an edge, would require 10TB of memory. We show in Section  that the Aspen and Terrace graph representations are significantly larger than this lower bound.
<FIGURE>