  Due to the dynamic nature of real-world graphs, there has been a growing
interest in the graph-streaming setting where a continuous stream of graph
updates is mixed with arbitrary graph queries. In principle, purely-functional
trees are an ideal choice for this setting due as they enable safe parallelism,
lightweight snapshots, and strict serializability for queries. However,
directly using them for graph processing would lead to significant space
overhead and poor cache locality.
  This paper presents C-trees, a compressed purely-functional search tree data
structure that significantly improves on the space usage and locality of
purely-functional trees. The key idea is to use a chunking technique over trees
in order to store multiple entries per tree-node. We design
theoretically-efficient and practical algorithms for performing batch updates
to C-trees, and also show that we can store massive dynamic real-world graphs
using only a few bytes per edge, thereby achieving space usage close to that of
the best static graph processing frameworks.
  To study the efficiency and applicability of our data structure, we designed
Aspen, a graph-streaming framework that extends the interface of Ligra with
operations for updating graphs. We show that Aspen is faster than two
state-of-the-art graph-streaming systems, Stinger and LLAMA, while requiring
less memory, and is competitive in performance with the state-of-the-art static
graph frameworks, Galois, GAP, and Ligra+. With Aspen, we are able to
efficiently process the largest publicly-available graph with over two hundred
billion edges in the graph-streaming setting using a single commodity multicore
server with 1TB of memory.
