[leftmargin=*,topsep=.5em]
GraphZeppelin:  We present a new high-performance streaming graph-processing system for computing the connected components of a graph. This system, which we call GraphZeppelin, uses new linear sketching data structures (CubeSketch, described below) to solve the streaming connected components problem and as a result requires a \(O(V/\log ^3(V))\) -factor less space than any lossless representation of the graph. GraphZeppelin is optimized for massive dense graphs: GraphZeppelin can process millions of edge updates (both insertions and deletions) per second, even when the underlying graph is far too large to fit in available RAM. As a result GraphZeppelin vastly increases the scale of graphs that can be processed.


CubeSketch: \(\ell _0\) -sampling optimized for graph connectivity sketching. We give a new \(\ell _0\) -sampling algorithm, CubeSketch, for vectors of integers mod 2. Given a vector of length \(n\)  and failure probability \(\delta \) , CubeSketch uses \(O(\log ^2(n)\log (1/\delta ))\)  bits of space and \(O(\log (n)\log (1/\delta ))\)  average time per update, which is a factor of \(O(\log (n))\)  faster than the best existing \(\ell _0\) -sampler for general vectors [1]}.

CubeSketch is a key subroutine in GraphZeppelin, where it is used to sample graph edges across arbitrary cuts as part of connected components computation. Here it is used to sketch vectors of length \({{V}{2}} = O(V^2)\) , where \(V\)  denotes the number of nodes in the graph. We show experimentally that CubeSketch is more than 3 orders of magnitude faster than the state-of-the-art \(\ell _0\)  sampling algorithm on graph streaming workloads.
In addition to the \(O(\log (V))\) -factor speedup, several non-asymptotic factors contribute to this performance improvement as well. First, the existing algorithm's average update cost is dominated by \(O(\log (V)\log (1/\delta ))\)  division operations, while CubeSketch's average update cost is dominated by \(O(\log (1/\delta ))\)  bitwise XOR operations, which are much faster. In addition, the general algorithm performs 128-bit arithmetic operations (including division) when processing graphs with more than \(10^5\)  nodes, whereas CubeSketch can use standard 64-bit operations to achieve the same error probability. Finally, both algorithms match the asymptotic space lower bound but CubeSketch uses roughly 4 times less space than the general algorithm.

Asymptotic guarantees of GraphZeppelin: space-optimality, I/O efficiency, \(O(\log ^3(V))\)  time per update. GraphZeppelin's core algorithm matches the \(O(V\log ^3(V))\) -bit space lower bound for the streaming connected components problem, and its average per-update time cost of \(O(\log (V))\)  is \(O(\log (V)))\)  times faster than the best existing algorithm [2]}. Additionally, GraphZeppelin can efficiently ingest stream updates even when its sketch data structure is too large to fit in RAM: its I/O complexity is \(sort(\text{length of stream}) + O(V/B\log ^3(V) + V\log ^*(V))\)  and for realistic block sizes it is an I/O-optimal external-memory algorithm [3]}. As a result, given a fixed amount of RAM and disk, GraphZeppelin is capable of efficiently computing the connected components of larger graphs than existing algorithms in the streaming or external memory models.

Empirical achievements of GraphZeppelin: better scaling for in-memory, out-of-core, and parallel computation, and undetectable failure probability. GraphZeppelin's CubeSketch-based design increases the size of input graphs that can be processed, scales well to persistent memory, and facilitates parallelism in stream ingestion. As a result, GraphZeppelin can ingest 2-5 million edge updates per second on a single scientific workstation (see Section ), both when its data structures reside completely in RAM and also when they reside on fast disk. As a result of these advantages, GraphZeppelin is faster and more scalable than the state of the art on large, dense graphs:
[topsep=.5em]
GraphZeppelin handles larger graphs for in-RAM computation. GraphZeppelin's space-efficient CubeSketch allows it to process graph streams larger than can be stored explicitly in a fixed amount of RAM and give it an asymptotic \({O}(V/ \log ^3(V))\)  space advantage over state-of-art systems on dense graphs. Given the polylogarithmic factors and constants, we need to determine the actual crossover point where GraphZeppelin processes graphs more compactly than Aspen and Terrace. We show empirically that this crossover point occurs when the space budget is between 32 and 64 gigabytes. That is, for dense graphs on several hundred thousand nodes, GraphZeppelin is \(40\%\)  more compact than Aspen and several times more compact than Terrace, and this advantage only increases for larger space budgets or input sizes. Additionally, for dense graph streams on \(2^{18}\)  nodes GraphZeppelin ingests updates 24 times faster than Terrace and twice as fast as Aspen.

GraphZeppelin can use persistent memory to handle even larger graphs. GraphZeppelin's node-based work buffering strategy facilitates out-of-core computation, allowing GraphZeppelin to use SSD to increase the scale of graph streams it can process while incurring a small cost to performance. We show experimentally that GraphZeppelin ingests updates more than two orders of magnitude faster than Aspen and Terrace when all systems swap to disk, and that using SSD slows GraphZeppelin stream ingestion by only 29%.

GraphZeppelin's stream ingestion is highly parallel. GraphZeppelin employs a node-based work buffering strategy that facilitates parallelism and improves data locality. We show experimentally that GraphZeppelin's multithreaded stream ingestion system scales well with more threads: its ingestion rate is 25 times higher with 46 threads than an optimized single-thread implementation.

GraphZeppelin's theoretical failure probability is undetectable in practice. GraphZeppelin and similar graph sketching approaches achieve their remarkable space efficiency at the cost of a random chance of failure. We show empirically that GraphZeppelin's observed failure rate is even lower than the proved (polynomially small) upper bound: in fact, for 5000 trials on real-world and synthetic graphs it never failed.


