Source-linked AI summary
Low-Latency Graph Streaming Using Compressed Purely-Functional Trees
Laxman Dhulipala, Julian Shun, Guy Blelloch
TL;DR
Dynamic graph streaming requires low-latency queries and updates, but ordinary purely-functional trees impose space and locality costs relative to compressed static representations. The paper introduces compressed C-trees and the Aspen framework, achieving faster, more memory-efficient streaming than Stinger and LLAMA while remaining competitive with static systems.
Problem
Graph-streaming systems must process interleaved updates and queries with low latency, while direct purely-functional-tree representations suffer space and locality disadvantages compared with CSR.
Method
The paper uses chunked compressed purely-functional C-trees and builds Aspen, a Ligra-based graph-streaming framework supporting concurrent queries and updates.
Results
Aspen is 1.8–10.2x faster than Stinger and 2.8–15.1x faster than LLAMA, while using 8.5–11.4x and 1.9–3.3x less memory, respectively.
Takeaways & Limitations
Aspen supports low-latency streaming on graphs with billions of vertices and hundreds of billions of edges, with performance comparable to state-of-the-art static frameworks.
Takeaways & Limitations
The LLAMA comparison is limited because its public code lacks streaming and batch-update support, cannot process the largest compressed inputs, and provides unreliable allocator statistics.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses low-latency graph streaming by combining compressed purely-functional trees with Aspen, a framework for concurrent queries and updates. Aspen improves memory and performance over streaming baselines while remaining close to static graph systems.
- 1 Introduction: C-trees chunk tree elements into contiguous arrays, reducing space usage and improving locality while retaining theoretically efficient tree operations.For integer graph elements, chunks can use difference coding and integer coding.
- 1 Introduction: Flat snapshots let global algorithms access each vertex’s edge-tree in O(1) work after O(n) work and O(log n) depth preprocessing.Local algorithms can instead amortize vertex-tree access against processing incident edges.
- 1 Introduction: Aspen extends Ligra with graph-update operations and supports concurrent, low-latency processing on graphs with billions of vertices and hundreds of billions of edges.The framework runs Ligra algorithms with minor modifications and targets a shared-memory machine with 1TB of RAM.
- 1 Introduction: Aspen is 1.8–10.2x faster than Stinger, 2.8–15.1x faster than LLAMA, and uses 8.5–11.4x and 1.9–3.3x less memory, respectively.These comparisons cover algorithm performance and memory usage against state-of-the-art graph-streaming frameworks.
- 1 Introduction: Aspen is 1.4x faster than GAP on average, 1.4x slower than Ligra+ on average, and 12x faster than Galois on average.Compared with Ligra+, Aspen requires 1.8–2.3x more space.
- 1 Introduction: Continuous edge updates change query performance by no more than 3%, while update throughput reaches 105M–442M updates per second in batches.Single-update throughput ranges from 11K–78K updates per second, and Aspen is an order of magnitude faster than Stinger even with very small batches.
2 Preliminaries
The preliminaries define graph notation, the work-depth analysis model, and purely-functional trees as mutation-free structures that preserve prior versions after updates.
- 2 Preliminaries: Graphs are denoted G(V, E), with n = |V| vertices and m = |E| edges; N(v) and deg(v) denote neighbors and degree.Vertices are indexed from 0 to n − 1, and weighted edges store real-valued weights.
- 2 Preliminaries: The work-depth model measures total operations as work and the longest sequential dependence as depth.This model is used to analyze the paper’s parallel algorithms.
- 2 Preliminaries: Purely-functional trees preserve previous versions after modification and return a new structure reflecting each update.The paper studies binary search trees in which each ordered element occupies a separate node and may have an associated value.
3 Compressed Purely-Functional Trees
C-trees compress purely-functional search trees by storing multiple elements in chunks attached to hashed head keys. The design improves locality and space usage while retaining efficient functional updates and search-tree operations.
- 3.1 C-tree Definition: C-trees promote hashed elements to heads stored in a tree, while non-head elements occupy contiguous tails and a possible prefix chunk.A fixed hash function ensures the same keys are promoted across trees, and chunks are variable-length arrays.
- 3.1 C-tree Definition: Figure 1 contrasts one-element-per-node purely-functional trees with C-trees, whose heads index contiguous non-head chunks.The prefix stores initial non-head elements without an associated head; each tail stores elements until the next head.
- 3.2 Space Usage and Locality: C-tree chunks have expected size b, contain O(b log n) elements at most with high probability, and use O(n/b) heads with high probability.These bounds follow from independently selecting each element as a head with probability 1/b.
- 3.2 Space Usage and Locality: A balanced C-tree over n elements has height O(log(n/b)) with high probability.The bound applies when the heads use a balanced binary tree.
- 3.2 Space Usage and Locality: Contiguous chunks amortize cache misses across multiple elements, while integer chunks can be compressed using difference encoding.Choosing b slightly larger than a cache line improves locality relative to separate tree nodes.
- 3.2 Space Usage and Locality: C-tree mapping and search retain the asymptotic work of purely-functional trees and O(log n) depth when chunks are small.Sequential chunk decoding does not change these bounds when b is constant and chunk size is O(log n) with high probability.
- 3.3 Other Approaches: Purely-functional B-tree updates copy B pointers per level, whereas C-tree updates copy one binary node per level and possibly one chunk.The C-tree node is 32 or 40 bytes in the implementation, while B-tree copying can involve thousands of bytes per level.
4 Operations on C-trees
C-tree operations support construction, search, mapping, splitting, and batch updates over compressed purely-functional trees. Union recursively combines tree structure and chunks while preserving ordering, with stated work and depth bounds for core operations.
- Operations on C-trees: C-tree primitives include Build, Find, Map, MultiInsert, and MultiDelete, with duplicate values combined during construction.
- Algorithms for Batch Insertions and Deletions: Union exposes a root from one C-tree, splits the other around its key, recursively unions corresponding subtrees, and joins the results.
- Algorithms for Batch Insertions and Deletions: Union splits tails and prefixes before recursion so elements crossing head boundaries merge with the corresponding chunks.
- Work and Depth Bounds: O(n log n) work and O(b log n) depth w.h.p. build a C-tree from a sequence of n elements.
- Work and Depth Bounds: O(b^2(k log((n/k) + 1))) expected work and O(b log k log n) depth support C-tree batch insertions and deletions.Here k = min(|T|, ...), as specified in the supplied bound passage.
5 Representing Graphs as Trees
Graphs are represented as a vertex-tree whose vertices store edge-trees, with C-trees and flat snapshots addressing the locality and access costs of functional trees. Batch updates and traversal techniques provide efficient graph processing over this representation.
- Representing Graphs as Trees: A graph uses a vertex-tree whose vertices store edge-trees, while directed graphs store separate out-neighbor and in-neighbor edge-trees.
- Representing Graphs as Trees: Batch edge updates sort edge pairs, build per-source edge trees, and combine them with existing edge-trees through Union.
- Representing Graphs as Trees: O(k log n) work and O(log^3 n) depth bound the batch update algorithm for updating the vertex-tree and affected edge-trees.
- Efficiently Implementing Graph Algorithms: Flat snapshots reduce edgeMap access from O(K log n) to O(K) by precomputing pointers to each vertex’s edge-tree.
- Efficiently Implementing Graph Algorithms: Flat snapshots speed BFS queries by an average of 1.26x on the input graphs.
- Efficiently Implementing Graph Algorithms: Vertex-access overhead can be amortized in local algorithms when average graph degree is at least comparable to log n.
6 Aspen Graph-Streaming Framework
Aspen extends Ligra with graph-update operations and version management over persistent graph representations. Its implementation supports concurrent readers and a writer while providing atomic operations and strict serializability.
- Aspen Graph-Streaming Framework: The interface extends Ligra with vertexSubsets, edgeMap, graph-update functions, and flat-snapshot support.
- Aspen Graph-Streaming Framework: Aspen’s acquire, set, and release operations support concurrent readers and a single writer without readers or writers blocking one another.
- Aspen Graph-Streaming Framework: Aspen guarantees strict serializability, making graph states and query outputs consistent with a serial execution respecting real time.
- Aspen Graph-Streaming Framework: Aspen stores the vertex-tree in an augmented purely-functional tree and stores each vertex’s incident edges in an integer C-tree.
7 Experiments
Aspen evaluates C-trees for concurrent graph streaming, showing strong compression, scalable algorithms, low-latency updates and queries, and competitive performance against streaming and static graph systems.
- Comparisons with graph-streaming systems: Aspen outperforms Stinger by 1.8–10.2x while using 8.5–11.4x less memory, and outperforms LLAMA by 2.8–7.8x while using 1.9–3.5x less memory.The LLAMA comparison covers supported static-graph experiments, while its public code lacks streaming and batch-update support.
- Chunking and compression: C-trees with difference encoding reduce memory usage by 4.7–11.3x versus uncompressed trees and improve application running times by 2.5–2.8x.Compression within chunks contributes an additional 1.2–2.3x memory reduction over uncompressed chunks.
- Parallel scalability of Aspen: Aspen achieves 46–78x speedups for BFS, betweenness centrality, and maximal independent set across inputs, while flat snapshots make BFS 1.12–1.34x faster.Flat-snapshot acquisition costs 15–24% of overall BFS time and becomes more profitable across repeated algorithms.
- Simultaneous updates and queries: Concurrent updates affect query performance by less than 3%, while edge visibility latency is at most 86 microseconds and can reach 12.7 microseconds.The experiment runs parallel BFS queries concurrently with an update stream using all available hardware threads.
- Batch updates: Parallel batch updates reach 442M updates per second on com-Orkut and 105M updates per second on Hyperlink2012 for batches of 2B updates.Deletion throughput is within 10% of insertion throughput and is usually faster.
- Static graph processing systems: Aspen is competitive with static graph systems, averaging 1.51x slower than Ligra+ across global algorithms while outperforming GAP by 1.4x on average.The broader comparison spans Aspen, Ligra+, GAP, and Galois across graph algorithms and inputs.
8 Related Work
Related systems differ in how they coordinate graph updates, queries, persistence, and compression. Aspen is positioned against these approaches through concurrent processing and higher update throughput.
- LLAMA uses version lists for persistence, but the paper argues such lists make achieving C-tree-level space usage challenging.
- Static graph frameworks such as Ligra+ support compressed graph processing, whereas temporal graph systems additionally support queries over historical graph states.
- Existing streaming frameworks either phase updates and queries or isolate queries on snapshots while updates create new snapshots.
- GraphOne supports concurrent queries and updates, while Aspen reports 94.5 million edges per second versus GraphOne’s 66.4 million on smaller and larger Twitter graphs, respectively.
- Graph databases can provide snapshot isolation for similar workloads, but transaction support adds overhead for graph analytics.
9 Conclusion
The paper introduces C-trees for efficient compressed purely-functional graph representation and uses them in Aspen for concurrent graph queries and updates. Aspen outperforms the compared streaming frameworks while remaining close to static-framework performance, with historical queries and incremental algorithms left for future work.
- C-trees provide theoretically efficient operations, low space usage, and good cache locality for purely-functional trees.
- Aspen uses C-trees to support concurrent low-latency graph queries and updates.
- Experiments show Aspen outperforms Stinger and LLAMA while incurring only modest overhead relative to state-of-the-art static graph frameworks.
- Future work includes incremental graph algorithms and historical queries using Aspen.
10 Appendix
The appendix describes parallel primitives, C-tree construction and operations, and their work-depth bounds. It details range handling, union and split procedures, and mapping over compressed trees.
- 10.1 Parallel Primitives: Scan computes prefix results from an array using an associative operator and identity element in O(n) work and O(log n) depth.
- 10.2 C-tree Construction: C-tree construction hashes elements into heads, builds tails and a prefix in parallel, and then builds a purely-functional tree over head-tail pairs.
- 10.3 Details on C-tree Primitives: C-tree UnionBC splits a prefix around the first key of another tree, unions matching ranges, and applies MultiInsert to produce the result.
- 10.3 Details on C-tree Primitives: UniqueKeyRanges packs each key’s first and last occurrence into key, start-index, and end-index triples for subsequent range unions.
- 10.3 Details on C-tree Primitives: Split returns two C-trees containing elements below and above a split key, with O(b log n) work and depth with high probability.
- 10.3 Details on C-tree Primitives: Batch updates support expected O(b^2(k log((n/k) + 1))) work and O(b log k log n) depth with high probability.