Select-Indexed Leaves for Compressed Dynamic Graphs

Graph systems that must absorb millions of edge insertions and deletions per second while still answering queries face a storage dilemma. Compressing each vertex's sorted neighbor list saves memory. The common compression, storing gaps between consecutive neighbor IDs as variable-length bytes, has a drawback: to find the 500th neighbor, or to check whether a given edge exists, you must decode every gap before it. Systems therefore cut neighbor lists into small blocks of about 128 elements, so that decoding stays cheap. We propose a different leaf: Elias-Fano encoding, which splits each neighbor ID into high bits written as a bit vector and low bits stored verbatim. A small "select" index on that bit vector (a lookup that returns the position of the $i$-th one bit in constant time) then lets any neighbor be read directly. Leaves can then grow to thousands of elements without slowing point access.

The parallel-algorithms side supplies the piece that makes this practical. A rank/select index (rank counts the one bits before a position; select finds the $i$-th one bit) can be built in parallel with little total work and short dependency chains, so rebuilding large leaves after each batch of edge updates need not become the bottleneck. Our core claim is that, in a purely functional compressed tree, leaf size is limited by sequential decoding rather than by anything fundamental. Removing that limit with work-efficient parallel select construction should give a dynamic graph store that uses fewer bits per edge and answers random-access queries (edge lookups, neighbor sampling, intersections) faster. Batch-update throughput should stay within a small factor of current designs. If a much simpler fix, adding sampled checkpoints to byte-coded blocks, gets the same result, the claim is wrong, and our experiments are designed to show that.

Where this sits

Two systems define the current design. Aspen stores adjacency in compressed purely functional trees. In these trees an update copies the root-to-leaf path instead of modifying in place, so readers always see a consistent snapshot. Aspen uses hash-chosen chunk boundaries and byte-coded gaps, and ingests 105M to 442M edge updates per second. PaC-trees / CPAM makes chunking deterministic, with leaves of $B$ to $2B$ elements and default $B=128$, using the same gap encoding. It reports 1.3x to 2.6x less space and 1.6x faster batch updates than Aspen. Both supply our host structure and its update discipline. Neither puts any index inside a leaf, and that missing index is the gap we target.

The leaf machinery comes from succinct data structures. Shun's improved parallel construction (with the earlier parallel wavelet tree construction) shows that rank/select over an $n$-bit vector builds in $O(n/\log n)$ work and $O(\log n)$ depth. We reuse that result directly for the select index on each leaf's high-bit vector. Orzo Elias-Fano-encodes the counters of a static rank index and cuts index overhead to 2.297%, but rank latency rises 9% to 38%. Orzo constrains our design: it warns that compressing the index itself costs query time. So we use Elias-Fano for the data, keep the select index uncompressed, and treat index overhead as a measured quantity.

Our proposal differs from these works in three ways. Orzo and Shun build static bit vectors, whereas our bit vectors are rebuilt inside a mutating, snapshot-preserving tree. CPAM stores the same data, but every in-leaf operation is a scan. Parallel Dynamic Spatial Indexes moves in the opposite direction, relaxing in-leaf order to speed up updates at the cost of query quality. We tighten in-leaf structure to speed up queries and ask what it costs updates.

Core Claim and Mechanism

A leaf holding sorted neighbors $x_1<\dots<x_b$ from universe $[0,u)$ is stored as $b$ low parts of $\ell=\lfloor\log_2(u/b)\rfloor$ bits each. The high parts go into a bit vector of about $2b$ bits in which element $i$ sets bit $(x_i \gg \ell) + i$. With a select index, access to $x_i$ takes $O(1)$. Successor search is a select on the zero bits followed by a short scan. The space is roughly $2+\log_2(u/b)$ bits per element, compared with at least 8 bits per element for byte codes.

The key structural fact is that encoding a merged sorted sequence is embarrassingly parallel. Once each element's rank $i$ is known from a prefix sum, its low bits and its high-bit position are independent writes. A batch update therefore becomes: route the batch to leaves as CPAM does, merge the old and new elements in parallel, write the Elias-Fano arrays, and build the select index with Shun's construction. The whole leaf rebuild costs $O(b)$ work and $O(\log b)$ depth.

The approach targets a fixed set of regimes. It is meant for workloads with batched ingestion and random-access-heavy queries, and for high-degree vertices where large leaves cut tree height and per-block metadata. It is not meant for single-edge latency. Copying a leaf of $b$ elements per isolated update is a real cost, and we will measure it rather than hide it. To reduce it, we test variable-size leaves, with small byte-coded leaves for low-degree vertices and select-indexed leaves above a degree threshold.

Research Program

We will implement the select-indexed leaf as a drop-in leaf type in CPAM's tree. It will reuse CPAM's join and expose operations, the block-aware primitives through which CPAM's set operations reach leaves, so union, difference, and filter work unchanged at the tree level. Inside a leaf we add three operations: access-by-index, successor, and leaf-level intersection that uses successor jumps. Batch-update cost will be analyzed in work and depth for a batch of $k$ edges touching leaves of size $b$. We expect $O(k\log(1+n/k) + (\text{touched leaves})\cdot b)$ work, which shows explicitly when large leaves hurt. The degree threshold for switching leaf types will be chosen by this cost model and checked empirically.

As a downstream test of maintenance rather than storage, we will store the non-tree-edge incidence lists of the linear-space Cluster Forest from Towards Scalable and Practical Batch-Dynamic Connectivity in these leaves. That system keeps every cluster's internal graph at diameter at most 2, so it can search for a replacement edge after a deletion in polylogarithmic depth. It reports 26 bytes per edge on Orkut, against 159 for the older level-based HDT structure. Its replacement search, like the doubling search of Parallel Batch-Dynamic Graph Connectivity, examines 1, 2, 4, … candidate edges per round. That round structure needs the $j$-th unexamined edge, which is a select on the leaf. The question is whether compressed incidence lists can bring the structure well below 26 bytes per edge without slowing deletions.

Baselines

The naive reference point is CPAM with its default byte-coded gap leaves at $B=128$ (PaC-trees). It is the strongest existing compressed dynamic graph store in the file, and it has been shown to beat Aspen in both space (1.3x to 2.6x) and batch-update speed (1.6x). We will run it from the same codebase, on the same machine and core count, with the same graph inputs and vertex orderings. We will also sweep its $B$ over the same range as ours, so that we do not compare our tuned leaf against its default. To beat it, our design must reach at least 20% fewer bits per edge, or at least 2x faster edge-existence queries and neighbor sampling, while losing at most 1.5x in batch-update throughput at batch sizes of $10^5$ and above. The file gives no CPAM bits-per-edge figure on these graphs (no reported result found on Lacuna for CPAM bits per edge on Orkut or Twitter), so we will measure it ourselves.

Aspen serves as a second, older reference. Its 105M to 442M updates per second (Aspen) sets the throughput scale. RadixGraph represents the non-functional, log-buffered design. It reports up to 16.27x faster updates than its best baseline and 40.1% memory savings, and it will be run on the LiveJournal, Orkut, and twitter-2010 inputs it was evaluated on. For connectivity, the baseline is the Cluster Forest implementation as published: 26 bytes per edge on Orkut, with 6.2x to 19.7x less memory and 1.4x to 6.2x faster updates than HDT. To beat it we need under 15 bytes per edge, with total update time no more than 1.2x worse.

The ablation that isolates our key ingredient is a byte-coded leaf with sampled checkpoints, storing an absolute value every $s$ elements, at matched index overhead. This keeps leaf size large but replaces select with sample-then-scan. If it equals our leaf on access and space, then Elias-Fano with select is not what matters. A second ablation keeps Elias-Fano but builds the select index sequentially per leaf. It measures whether parallel construction affects batch throughput for high-degree vertices.

Why not just…?

Why not just keep byte-coded gaps in 128-element blocks? For uniform scans such as BFS and PageRank, CPAM's leaves may well remain as fast or faster, and we expect them to. Small blocks, however, fix the per-block metadata and tree-height costs, and byte codes cannot go below 8 bits per element. Orzo's 9% to 38% latency penalty (Orzo) shows that decoding overhead is real, so scan-heavy kernels are where we expect to lose. The experiments report them separately and do not average them away.

Why not just add sampled checkpoints to byte-coded blocks? This is the serious threat. It is cheap, compatible with SIMD instructions, and gives near-constant access with tunable overhead. It cannot match Elias-Fano's space on graphs whose gaps are mostly small but whose universe is large, and its access still requires a scan of length $s$. Our first ablation runs this alternative at matched overhead. If it matches us within 10% on space and access, we will report the more modest result: larger leaves help, and Elias-Fano does not.

Why not just buffer updates in a log and merge lazily, as RadixGraph does? Log buffering gives cheap amortized updates, but the file notes that it leaves consistent multi-vertex snapshots open, which functional trees provide by construction. The two ideas also compose: a buffer could sit in front of our leaves. We therefore compare against RadixGraph on raw throughput, and separately test a buffered version of our leaf, so that the result does not depend on which update path is used.

Why not just rebuild a static compressed graph periodically? Aspen already runs within about 1.4x of static frameworks without rebuilds. Rebuilds also cause latency spikes, and DiskANN's streaming results show that indices left without maintenance degrade. We include a periodic parallel rebuild of a static Elias-Fano graph as an upper bound on query speed and space. This shows how much of the static ideal the dynamic leaf recovers.

Proposed Experiments

The graphs are Orkut, LiveJournal, Twitter (2.4B edges), and Friendster. Hyperlink2012 is included if memory allows, which tests whether the space savings extend single-machine reach as Aspen did at 225B edges. The synthetic g500-24 and uni-24 graphs separate skewed from uniform degree distributions. All systems run on one multicore server with an identical thread count.

The metrics are bits per edge, and batch-update throughput across batch sizes from $10$ to $10^7$. Single-update latency is reported separately. Query workloads are edge-existence queries, uniform random-neighbor sampling inside random walks, triangle counting (which stresses leaf intersection), and BFS (which stresses scans).

The decisive checks are three. The first is a Pareto plot of bits per edge against update throughput for CPAM swept over $B$, sampled byte codes, and our leaf. Our leaf must lie strictly outside the other curves somewhere. The second is the access-latency gap against the sampled-checkpoint ablation, which settles the main threat. The third is Cluster Forest bytes per edge on Orkut against the reported 26, with deletion time held within 1.2x. A negative result on any of these narrows the claim to the regime where it holds, and we will report it that way.