arXiv CSopen access

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs

arXiv:2605.15173v1 [cs.DS] 14 May 2026

Hybrid Sketching Methods for Dynamic Connectivity on Sparse Graphs Quinten De Man∗

Gilvir Gill∗

University of Maryland College Park, MD, USA [email protected]

Stony Brook University Stony Brook, NY, USA [email protected]

Michael A. Bender

Laxman Dhulipala

David Tench

Stony Brook University Stony Brook, NY, USA [email protected]

University of Maryland College Park, MD, USA [email protected]

Lawrence Berkeley National Lab Berkeley, CA, USA [email protected]

Abstract Dynamic connectivity is arguably the most basic and fundamental dynamic graph problem, and recent algorithmic breakthroughs on dynamic graph sketching have reshaped what is theoretically possible for the problem: by encoding the graph as per-vertex linear sketches, these algorithms solve dynamic connectivity in only Θ(𝑉 log2 𝑉 ) space, independent of the number of edges, with an asymptotic advantage over lossless Θ(𝑉 + 𝐸)-space structures that grows as the graph becomes denser. Prior to this work, no practical dynamic connectivity algorithm has been able to translate these theoretical breakthroughs into space savings on real-world graphs. The main obstacle is that per-vertex sketches cost thousands of bytes per vertex, so sketching only pays off once the graph becomes extremely dense. Our starting observation is that real-world graphs that are sparse on average are often not uniformly sparse—these graphs can contain dense cores on a small subset of the vertices that accounts for a large fraction of the edges. We exploit this structure via hybrid sketching: sketch only the dense core, and store the sparse periphery losslessly. On the theoretical side, we design new hybrid algorithms for both fully-dynamic and semi-streaming connectivity with space 𝑂 (min{𝑉 +𝐸, 𝑉 log 𝑉 log(2 +𝐸/𝑉 )}) w.h.p., simultaneously matching the lossless bound on sparse graphs, the sketching bound on dense graphs, and improving on both in an intermediate regime. A key technical ingredient is BalloonSketch, a new ℓ0 -sampler that reduces per-vertex sketch sizes by up to 8× on real-world graphs. We give a practical C++ implementation of our new algorithms in HybridSCALE, a modular system that treats the lossless and sketchbased components as subroutines. To our knowledge, HybridSCALE is the first sketch-based dynamic connectivity system to save space on commonly studied real-world graphs. Compared to the state-ofthe-art lossless baseline, HybridSCALE uses up to 15% less space on sparse real-world graphs (average degree < 100), up to 92% less space on intermediate density graphs (average degree ≈ 100–1000), and up to 97% less space on synthetic dense graphs (average degree > 1000).

1

Introduction

Graph data and graph algorithms play a fundamental role in modern computing, underlying applications in web search, transactional systems, and scientific computing, among many other areas. In nearly all of these settings, the underlying graph is inherently dynamic: ∗ Both authors contributed equally to this research.

edges are continually inserted and deleted into the graph as the state of the system evolves (e.g., as transactions are performed). Maintaining basic structural queries on a graph as it changes is therefore a foundational primitive for downstream analytics, and dynamic connectivity (answering whether two vertices currently lie in the same connected component as the edge set changes) is arguably the most fundamental and well-studied dynamic primitive [16, 26, 29, 30, 32– 37, 46, 57, 59]. Despite a four-decade old theoretical foundation, translating these results to practical systems has proven extremely difficult, and dynamic connectivity remains an active frontier for both theoretical and practical research. Recent experimental work on dynamic connectivity pursues two broad approaches, each with distinct trade-offs. The first approach is using lossless dynamic data structures where every edge in the graph is maintained within the structure. Lossless systems use Θ(𝑉 + 𝐸) space and are reasonably space-efficient for sparse inputs where 𝐸 is not much larger than 𝑉 . The second approach is to use graph sketching, which encodes the graph as a collection of vertex-level linear sketches and solves dynamic connectivity in Θ(𝑉 log2 𝑉 ) space, i.e., in space that is not dependent on the number of edges. The attraction and promise of graph sketching is that it remains space-efficient even as the graph becomes arbitrarily dense, while lossless methods would continue to use space linear in the number of edges. Sketching techniques have found massive success in applications across computer science, particularly in streaming algorithms for networking and data analytics where sketches can exponentially reduce the space requirements of fundamental analytical tasks [5, 19, 25, 38]. However, in graph sketching each vertex requires its own sketch, so the total space requirement is significantly higher than the polylogarithmic space achieved by sketching in other domains. Specifically, per-vertex graph sketches require Θ(polylog(𝑉 )) words, translating to thousands of bytes per vertex. Thus, sketching only beats storing the edges in an adjacency list when the average degree is at least in the thousands. However, the average degrees of real-world graphs are typically at most in the hundreds, which is at least an order of magnitude below this break-even point when every vertex is sketched. For example, on the Orkut social media graph (𝑉 ≈ 3.07 million, average-degree 76.3) [43], the state-of-the-art sketch-based dynamic connectivity system, CUPCaKE [22], would require roughly 36× more space than the state-of-the-art lossless system, an implementation of Cluster Forest [21].

Despite an elegant and influential body of theory [15, 44, 58], existing sketching systems [55, 56] have demonstrated space savings only on synthetic dense inputs such as Kronecker graphs and high-density Erdős–Rényi graphs. In this paper we study whether we can carefully leverage graph sketching to obtain more space-efficient dynamic connectivity data structures even on sparse real-world datasets. Crucially, graphs that are sparse on average are typically not uniformly sparse. For example, social networks, web graphs, citation graphs, and collaboration networks, among others, are sparse on average but often contain a small, densely interconnected core that accounts for a large fraction of the edges [6, 8, 11, 14, 27, 39, 43, 47, 50]. On such graphs, the cost of sketching vertices in the core would be worthwhile, but would be prohibitive if blindly applied to every vertex. This observation suggests a natural strategy: sketch only the dense core, and store the sparse periphery losslessly. We refer to this approach as hybrid sketching. Although the idea is straightforward to state, realizing it both in theory and in practice requires carefully understanding how to combine each of the three moving parts (the graph sketching system, the lossless structure, and the logic that routes edges between them). There are three major challenges in the way of designing a hybrid sketching method: (1) We must find a space-minimizing partition of the graph into a sketched core and lossless periphery with no prior structural knowledge. We also desire high update throughput and low query latency. Further, the partitioning scheme must keep the lossless and sketch representations consistent. (2) Since the graph is dynamic, the boundary between the dense core and the sparse periphery may change over time. Moving edges from the core to the periphery requires recovering them from the sketch data structure. However, classical connectivity sketches do not guarantee returning all edges, only some of the sketched support. Hybrid sketching therefore requires leveraging a sparse recovery sketch that returns the full support of a sparse vector with high probability. (3) The state-of-the-art implementations of ℓ0 -samplers, the main building block underlying graph sketching, have a space overhead of thousands of bytes per-vertex. As a result, these sketches don’t save space over a lossless representation until the degree is in the thousands. Commonly-studied real-world graphs rarely have average degree higher than the low hundreds, so asymptotically smaller ℓ0 -samplers are likely required to save space. In this paper we introduce theoretically-efficient and practical techniques for implementing hybrid sketching algorithms, together with an accompanying system that sketches only the dense portion of a graph while storing the rest losslessly. To address the first challenge, we develop a hybrid framework that routes edges between a sketched dense core and a losslessly stored sparse periphery as the graph evolves, preserving the semantics of connectivity queries endto-end. Regarding the second challenge, works on Invertible Bloom Lookup Tables (IBLTs) provide a sketching primitive to recover the entire support of a sparse vector with high probability [9, 31]. To address the third challenge, we design BalloonSketch, an ℓ0 -sampler whose aggregate space usage tracks the true support size of the sketched vector rather than the universe size, improving on the best known ℓ0 -sampling space bound when the vector is sparse. 1 Code is at https://github.com/GraphStreamingProject/HybridDynamicQueriesCC.

Taken together, these contributions yield the first hybrid sketching algorithms for dynamic connectivity whose space usage simultaneously matches the lossless bound on sparse inputs, matches the sketching bound on dense inputs, and improves on both in the intermediate regime. We realize these algorithms in a system, HybridSCALE 1 , which to our knowledge is the first sketch-based dynamic connectivity system to deliver space savings on real-world graphs. Next, we give a more technical description of our contributions.

1.1

Our Contributions

Our main theoretical results are new hybrid sketching algorithms for graph connectivity with strong space complexity on both sparse and dense graphs. Their key property is that their space complexity simultaneously matches the asymptotic space of lossless methods on sparse inputs and of sketching-based methods on dense inputs, and improves on both in the intermediate regime. Theorem 1.1 (Hybrid Dynamic Connectivity). There exists a dynamic connectivity algorithm with space complexity     𝐸 w.h.p. 𝑂 min 𝑉 + 𝐸, 𝑉 log(𝑉 ) log 2 + 𝑉 The update complexity is amortized 𝑂 (log4 𝑉 ). The query complexity is worst-case 𝑂 (log 𝑉 /log log 𝑉 ). We additionally give a hybrid algorithm for the semi-streaming model, in which the graph arrives as a stream of edge insertions and deletions under an 𝑂 (𝑉 polylog(𝑉 )) memory budget, and connectivity queries are answered from the final sketch rather than continuously during the stream [3, 4, 28, 42, 45]. This is the classical setting in which graph sketching was originally developed, and it remains the standard benchmark for evaluating sketch-based space complexity. Our algorithm achieves the same hybrid space bound as in the fully-dynamic setting, with asymptotically faster update complexity in exchange for slower one-shot queries. Theorem 1.2 (Hybrid Streaming Connectivity). There exists a semi-streaming algorithm for connectivity on polynomial-length input streams of edge updates with space complexity     𝐸 𝑂 min 𝑉 + 𝐸, 𝑉 log(𝑉 ) log 2 + w.h.p. 𝑉 The update complexity is amortized Θ(log 𝑉 ) w.h.p. The query complexity is worst-case Θ(𝑉 log2 𝑉 ). The hybrid bounds above rest on a new sketching primitive, BalloonSketch, which we believe is of independent interest. This result improves on the best known ℓ0 -samplers, which use Θ(𝐿 log 𝑛) space, by replacing the universe-size dependence with a dependence on the true support size 𝑚. This improved sketch algorithm results in up to a 8× reduction in per-vertex sketch size on sparse real-world graphs. We find that this space reduction is necessary for our hybrid sketching algorithm to be space-efficient on these inputs. Theorem 1.3 (BalloonSketch). There exists an ℓ0 -sampler, BalloonSketch, such that given 𝐿 independent BalloonSketches, each sketching the same vector 𝑥 ∈ F𝑛 with 𝑚 = ∥𝑥 ∥ 0 : (1) The total space usage of the sketches is 𝑂 (𝐿 log 𝑚 + log 𝑛) w.h.p. (2) The total cost of one update to each sketch is 𝑂 (𝐿 + log 𝑛) w.h.p.

The HybridSCALE system. We realize the hybrid framework in HybridSCALE, a modular dynamic connectivity system whose design separates the lossless and sketch-based components. Any lossless dynamic connectivity structure can be plugged in on one side, and any sketch-based one on the other. Our implementation uses an implementation of Cluster Forest [1, 2, 21] on the lossless side. For the sketch-based side, we implemented a new system, BalloonDC, combining ideas from Gibb’s algorithm [30], CUPCaKE [22], and our new sketching primitive BalloonSketch. To our knowledge, HybridSCALE is the first graph sketching system to deliver space savings on commonly studied real-world graphs. Compared to the state-of-the-art lossless baseline, HybridSCALE uses up to 15% less space on sparse real-world graphs (average degree < 100), up to 92% less space on intermediate density graphs (average degree ≈ 100–1000), and up to 97% less space on synthetic dense graphs (average degree > 1000). Update and query throughput remain competitive with both pure baselines.

2 Preliminaries 2.1 Semi-Streaming and Dynamic Graph Models In the graph semi-streaming model [28], an algorithm is presented with a stream of edge insertion or deletion updates that define a graph. The challenge in this model is to compute some property of the graph given a single pass over the stream and memory sublinear in the size of the graph. Specifically, stream 𝑆 defines a graph G = (V, E) with 𝑉 = |V | and 𝐸 = |E |. Each update has the form ((𝑢, 𝑣), Δ) where 𝑢, 𝑣 ∈ V, 𝑢 ≠ 𝑣 and Δ ∈ {−1, 1} where 1 indicates an edge insertion and −1 indicates an edge deletion. In this paper we study the semi-streaming connected components problem which returns a spanning forest of the graph at the end of the stream. In the dynamic graph model, the challenge is to be able to efficiently query a specific structural property of a changing graph at any time. Specifically the algorithm is given a sequence 𝑆 of updates (InsertEdge(𝑒) or DeleteEdge(𝑒)) which must be processed in order. Any prefix of the first 𝑖 updates in 𝑆 defines a graph G𝑖 = (V𝑖 , E𝑖 ). Immediately after processing the 𝑖-th update , one or more queries may be issued and the algorithm must compute the answers for graph G𝑖 before receiving the 𝑖 + 1-th update. In this paper we study the dynamic connectivity problem, where the structural property of interest is connectivity, and queries of the form Connected(𝑢, 𝑣) return whether vertices 𝑢 and 𝑣 are connected in G𝑖 .

2.2

Linear Sketching for Streaming Connectivity

Ahn. et. al. ([3]) introduced the first semi-streaming algorithm for connected components using O (𝑉 log2 𝑉 ) space. The core innovation of this approach is that the algorithm represents each vertex’s adjacency list as a compact linear sketch of its characteristic vector. 𝑉 For a vertex 𝑣, its characteristic vector 𝑓𝑣 ∈ R ( 2 ) encodes its incident edges such that for any edge (𝑢, 𝑤), the entry 𝑓𝑣 ((𝑢, 𝑤)) is 1 if𝑣 = 𝑢 and (𝑢, 𝑤) ∈ E, −1 if 𝑣 = 𝑤 and (𝑢, 𝑤) ∈ E, and 0 otherwise. This specific encoding ensures that for any subset of vertices 𝑆 ⊆ V, the Í sum of their vectors 𝑣 ∈𝑆 𝑓𝑣 isolates the cut (𝑆, V \𝑆). Every internal edge within 𝑆 is added twice and cancels out perfectly, leaving only the edges that cross between 𝑆 and the rest of the graph. Storing characteristic vectors explicitly would require O (𝑉 3 ) total space. To solve this, the streaming algorithm compresses them using an ℓ0 -sampler.

Definition 2.1. An algorithm S is an ℓ0 -sampler with failure probability 𝛿 ∈ (0, 1) if it can process coordinate updates to a vector 𝑥 and maintain a compact sketch S(𝑥) satisfying: (1) Sampleable: If 𝑥 is non-zero, sampling the sketch returns a uniform random non-zero coordinate with probability at least 1 − 𝛿. (2) Linear: For any vectors 𝑥 and 𝑦, S(𝑥) + 𝜆S(𝑦) = S(𝑥 + 𝜆𝑦). With constant 𝛿, the ℓ0 -sampler from Ahn et al. [3] has space, update, and sampling complexity 𝑂 (log 𝑉 ). In Section 3.1 we provide more details about a more recent ℓ0 -sampler, CameoSketch [56], as well as our new ℓ0 -sampler, BalloonSketch. Because ℓ0 -samplers are linear, the streaming algorithm can compute an ℓ0 -sampler for an entire component’s cut simply by summing Í the sketches of its individual vertices: 𝑣 ∈𝑆 S(𝑓𝑣 ). By maintaining Θ(log 𝑉 ) independent sketches per vertex, the algorithm can sum the sketches of any merged component (supernode) to successfully sample an outgoing edge. Repeating this process simulates the Θ(log 𝑉 ) rounds of Borůvka’s algorithm required to recover a spanning forest. Tench et. al. provided the first practical implementation of the AGM sketch in GraphZeppelin [55] by introducing CubeSketch, a specialized ℓ0 -sampler that operates over F2 rather than Z. The current state-of-the-art ℓ0 -sampler, CameoSketch [56] (see Section 3.1), builds on this foundation by further improving CubeSketch’s worstcase running time and sampling success probability.

2.3

Dynamic Connectivity

Lossless Dynamic Connectivity. Traditional dynamic connectivity algorithms all store a data structure containing a lossless representation of the graph. We refer to these as lossless dynamic connectivity algorithms. The best algorithms, such as Cluster Forest [59], have 𝑂 (𝑉 + 𝐸) space usage, 𝑂 (log2 𝑉 ) or better (amortized) update time, and 𝑂 (log 𝑉 ) or better query time. De Man et al. [21] provided a practical implementation of the Cluster Forest algorithm. Sketch-Based Dynamic Connectivity. More recently, a new class of dynamic connectivity algorithms has emerged which combines both the polylogarithmic update and query times of traditional lossless dynamic connectivity algorithms and the small space usage of streaming connectivity algorithms [30, 37]. We call these sketch-based dynamic connectivity algorithms. The best known sketch-based algorithm, Gibb’s algorithm [30], uses 𝑂 (𝑉 log2 𝑉 ) space, processes updates in 𝑂 (log4 𝑉 ) time, and answers queries in 𝑂 (log 𝑉 /log log 𝑉 ) time. Each query is correct w.h.p. The core component of Gibb’s algorithm is the cutset [37]. For a graph G = (V, E) and a spanning forest F = (V, E F ), it can find an edge crossing a component’s cut during dynamic updates. Letting C(𝑤) be the forest component containing 𝑤, a cutset supports: • Link(𝑢, 𝑣): Insert edge (𝑢, 𝑣) ∉ E F into F , merging C(𝑢)/C(𝑣). • Cut(𝑢, 𝑣): Remove edge (𝑢, 𝑣) ∈ E F from F , splitting C(𝑢, 𝑣). • Update(𝑒): Insert edge 𝑒 into E (if absent) or delete it (if present). • Query(𝑣): Return an edge crossing the cut of C(𝑣) with constant success probability 𝑝. Cutsets are implemented via a dynamic tree augmented with an ℓ0 -sampler S(𝑓𝑣 ) for each vertex 𝑣. The dynamic tree must support subtree aggregate queries using a commutative, associative function (in this case sketch addition). Due to ℓ0 -sampler linearity, querying a component’s subtree returns the sum of its vertices’ sketches, which

encodes the cut between the component and the rest of the graph. Cutsets typically use 𝑂 (𝑉 log 𝑉 ) space, perform Links, Cuts, and Updates in 𝑂 (log2 𝑉 ) time, and Query in 𝑂 (log 𝑉 ) time. Gibb’s algorithm maintains cutsets 𝐹 0, . . . , 𝐹𝑡𝑜𝑝 (where 𝑡𝑜𝑝 = Θ(log 𝑉 )) across successive forest levels F0 ⊆ · · · ⊆ F𝑡𝑜𝑝 . Higher levels track increasingly larger components, ultimately yielding the true connected components. It also maintains a separate dynamic tree T supporting maximum-weight path queries, where tree edges match E F𝑡𝑜𝑝 and an edge’s weight is the lowest level 𝑖 that the edge appears in F𝑖 . The algorithm ensures three invariants: (1) F0 = (V, ∅). (2) F𝑖 ⊆ F𝑖+1 for 0 ≤ 𝑖 < 𝑡𝑜𝑝. (3) For 0 ≤ 𝑖 < 𝑡𝑜𝑝, if a Query on 𝐹𝑖 for a component C ∈ F𝑖 succeeds, C is a proper subset of some C ′ ∈ F𝑖+1 . Gibb et al. show that if these invariants hold then F𝑡𝑜𝑝 is a spanning forest of G w.h.p. They also provide an update algorithm which maintains these invariants w.h.p., and takes𝑂 (log4 𝑉 ) time. Consequently, queries are correct w.h.p. across polynomially many updates.

3

Hybrid Streaming Connectivity

As a first step towards our main result of a hybrid dynamic connected components algorithm, we present a new semi-streaming algorithm for connected components that uses asymptotically less space than any existing algorithm. We begin by carefully stating the nature of the space advantage. Among the existing algorithms for streaming connectivity, there is no clear winner in terms of asymptotic space usage. This is because some lossless algorithms achieve an 𝑂 (𝑉 + 𝐸) space bound, which is optimal for sparse graphs, while some sketching algorithms achieve a 𝑂 (𝑉 log2 𝑉 ) space bound which is optimal for dense graphs. The lossless algorithms are suboptimal on dense graphs, and similarly sketch algorithms are suboptimal on sparse graphs. In contrast, we present a semi-streaming algorithm for connected components that simultaneously matches the state-of-the-art space usage for sparse graphs and dense graphs. In fact in a certain density range, our algorithm uses asymptotically less memory usage than all prior algorithms. Specifically, when the input graph has Ω(𝑉 1+𝜀 ) edges for 0 < 𝜀 ≤ 1, our algorithm uses 𝑂 (𝑉 log2 𝑉 ) words of space, matching the space of Ahn et al. [3] (sketching approach). When the input graph has O (𝑉 log 𝑉 log log 𝑉 ) edges, our algorithm uses the same space as an adjacency list representation (lossless approach): 𝑂 (𝑉 + 𝐸). When the input graph has 𝑜 (𝑉 1+𝜀 ) edges and 𝜔 (𝑉 log 𝑉 log log 𝑉 ) edges, our algorithm uses asymptotically less space than both Ahn et al. and an adjacency list representation. Theorem 1.2 summarizes our result. Figure 1 depicts the relative asymptotic space usage of a lossless approach, a sketching approach, and our new hybrid approach. Theorem 1.2 (Hybrid Streaming Connectivity). There exists a semi-streaming algorithm for connectivity on polynomial-length input streams of edge updates with space complexity     𝐸 𝑂 min 𝑉 + 𝐸, 𝑉 log(𝑉 ) log 2 + w.h.p. 𝑉 The update complexity is amortized Θ(log 𝑉 ) w.h.p. The query complexity is worst-case Θ(𝑉 log2 𝑉 ). Hybrid Streaming Connectivity Overview. The main idea behind this result is to lossily store the incidence lists of high-degree vertices

as ℓ0 sketches, while storing the incidence lists of low-degree vertices losslessly (as an explicit set of neighboring vertices). Specifically, we set a fixed density threshold 𝛿, and we call any vertex 𝑢 whose degree is higher than 𝛿 heavy, and otherwise call 𝑢 light. For each heavy vertex, we maintain an ℓ0 sketch of the characteristic vector (see Section 2.2) of its incidence list, and for each light vertex we store its incidence list losslessly (as an explicit set). As we will see, setting 𝛿 appropriately minimizes the total size of the data structure, which results in Theorem 1.2. To make this idea work, we require two sketching primitives (one existing and one new) which we now describe. First, note that as the input stream progresses, vertices that were once light may become heavy and vice versa. In particular, when the degree of a heavy vertex 𝑢 decreases below 𝛿, its edges must be stored losslessly instead of in sketch form. We must therefore recover 𝛿 edges from the sketch of 𝑢, but existing ℓ0 sketching algorithms only guarantee recovery of Θ(log 𝑉 ) edges with high probability. To address this problem, we also maintain an invertible bloom lookup table (IBLT) [31] over the set of neighbors for each heavy vertex. An IBLT is a compact data structure representing a set of elements that ensures the successful recovery of all elements in the set with high probability, provided the size of the set is currently below a fixed threshold 𝑟 . Regardless of the size of the represented set, the IBLT always uses 𝑂 (𝑟 ) space. Specifically, we use a recent tunable version of IBLT [9] and configure it to be successful with high probability in 𝑉 . This results in 𝑂 (𝑟 ) space usage, 𝑂 (log2 𝑉 ) insertion time, and 𝑂 (𝑟 ) time to recover all elements (decode). Second, we present (in Section 3.1) a more compact ℓ0 -sampling primitive, which we call BalloonSketch. When the vertex being sketched has high degree, BalloonSketch’s space matches that of existing ℓ0 samplers with constant success probability: 𝑂 (log 𝑉 ). But unlike existing ℓ0 sampling algorithms, the size of BalloonSketch is 𝑂 (log(𝑑)) in expectation where 𝑑 is the degree. The key insight is that when the degree is low, in expectation much of the traditional ℓ0 sampler data structure is empty. BalloonSketch exploits this fact to minimize space via aggressive dynamic resizing. Since each vertex has𝑂 (log 𝑉 ) ℓ0 samplers, we are then able to show that the total space across all the 𝑂 (𝑉 log 𝑉 ) samplers is 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. Finally, in Section 3.2 we combine the ideas of a density threshold 𝛿, IBLT, and BalloonSketch to prove Theorem 1.2. We show that setting the density threshold 𝛿 to Θ(log 𝑉 log log 𝑉 ) results in the space bound from Theorem 1.2. This value of 𝛿 is essentially the minimum degree at which a vertex can use asymptotically less space storing its incidence list in BalloonSketch form (i.e. log 𝑉 log 𝑑 ≤ 𝑑 when 𝑑 = Ω(log 𝑉 log log 𝑉 )). To facilitate efficient updates while maintaining the space bound, we only recover the lossless incidence list of a vertex that became light when the degree becomes ≤ 𝛿/2. When a vertex becomes heavy (degree > 𝛿), we convert its lossless incidence list to a BalloonSketch by initiating a new sketch and updating it 𝛿 + 1 times, and also instantiate an IBLT for the vertex.

3.1 ℓ0 -Sampling and BalloonSketch This section introduces BalloonSketch, a new sketching primitive for ℓ0 sampling that uses less space on sparse vectors than prior methods. First we summarize CameoSketch [56], the prior state-ofthe-art algorithm for ℓ0 sampling, and introduce several important definitions that will be used in our definition of BalloonSketch.

• Residual Depth: Let 𝑤 := ⌈log2 (𝑚)⌉ be the index of the bucket where we mathematically expect exactly one non-zero coordinate to land. The residual depth of a sketch is its actual depth minus this expected depth 𝑤 (or 0 if the actual depth is < 𝑤). • Sketch Matrix: A sequence of 𝐿 sketches (Cℎ1 , . . . , Cℎ𝐿 ) with independent hash functions. By utilizing multiple independent sketches, the matrix boosts the psuccess probability. With 𝐿 = Ω(log 𝑛), the matrix yields Θ(𝐿) successful samples w.h.p. in 𝑛.

Lossless: O(V + E) 2

Sketching: O(Vlog V)

Space

Hybrid: O(min{V + E, Vlog Vlog(2 + E/V)})

Density (|E|)

(2 ) V

Figure 1: A plot visualizing the space complexity of various graph streaming approaches. Each function is plotted with a fixed |𝑉 | = 250. The 𝑥-axis varies the value of |𝐸|.

Prior Work and Definitions for ℓ0 -Sampling. The core goal of the CameoSketch algorithm is to act as an ℓ0 -sampler over vectors in F𝑛2 . It achieves this by geometrically distributing the coordinates of an input vector across a series of buckets, ensuring a high probability of isolating a single non-zero coordinate. A CameoSketch Cℎ is a sequence of 𝜌 = Θ(log 𝑛) sketch buckets 𝐵 = [𝑏 0, . . . , 𝑏 𝜌 −1 ]. Each coordinate 𝑣 ∈ [𝑛] is assigned to exactly two of these buckets: it is always placed in𝑏 0 , designated as the deterministic bucket, and it is also placed in a second random bucket 𝑏𝑖 chosen geometrically at random. This second assignment is driven by a Θ(1)-wise independent hash function ℎ : [𝑛] → [2𝜌 ] (drawn from a family H ); specifically, 𝑣 is assigned to bucket 𝑖 = max{𝑑 ∈ N | ℎ(𝑣) ≡ 0 (mod 2𝑑 )}. This explicitly simulates a coin-flipping process, ensuring the probability of landing in 𝑏𝑖 is Pr [𝑣 ∈ 𝑏𝑖 ] = 1/2𝑖 . Each bucket𝑏𝑖 maintains a lossy representation of the coordinates assigned to it. It stores two integer values, 𝑏𝑖 .alpha and 𝑏𝑖 .gamma, both taking Θ(log 𝑛) bits and initialized to 0. When a coordinate 𝑗 of the input vector 𝑥 is updated, we compute ℎ( 𝑗) to find its assigned bucket 𝑏𝑖 , and perform the following bitwise XOR operations: • 𝑏𝑖 .alpha ← 𝑏𝑖 .alpha ⊕ 𝑗 • 𝑏𝑖 .gamma ← 𝑏𝑖 .gamma ⊕ 𝛾 ( 𝑗) (where 𝛾 is a 2-wise independent hash function)

BalloonSketch. Now we present our new sketching primitive for ℓ0 -sampling, BalloonSketch. The key benefit of BalloonSketch is that it has an asymptotic space advantage over CameoSketch and all existing ℓ0 -samplers on sparse vectors. On dense vectors, it matches the asymptotic space complexity of CameoSketch. In a sketch matrix with large enough size, updates to BalloonSketch are as efficient as updates to CameoSketch. The sampling success probability and the cost of sampling for a BalloonSketch are identical to CameoSketch. Definition 3.1 defines a BalloonSketch: Definition 3.1 (BalloonSketch). A BalloonSketch is a sequence of sketch buckets stored in a dynamically allocated container. The size of the container is always resized to the sketch depth. Unlike CameoSketch which statically allocates Θ(log 𝑛) buckets, BalloonSketch avoids storing the empty buckets deeper than its sketch depth. Its space usage is therefore proportional to its depth. The procedures for assigning coordinates to buckets and updating the BalloonSketch are almost identical to those of CameoSketch. However, if an update changes the depth of the sketch, then the bucket list must shrink or grow. The pseudo-codes for the BalloonSketch algorithms are given in Algorithm 1.

Algorithm 1 BalloonSketch Algorithms 1: function initialize(𝑛) 2: 3:

𝐵 ← [], 𝜌 ← lg(𝑛) + Θ(1) Let ℎ : ⟨𝑛⟩ → [2𝜌 ] be drawn from a family of Θ(1)-wise independent hash functions.

4: function sample 5: 6: 7: 8:

if 𝐵 == [] then return “empty” for 𝑖 = 𝐵.size to 0 do if 𝐵 [𝑖] is good then return (“good”, 𝐵 [𝑖].value) return “fail”

Maintaining the buckets this way grants us these two properties: 9: function reallocate(ℓ)

(1) w.h.p. 𝑏𝑖 .alpha = 0 and 𝑏𝑖 .gamma = 0 if and only if the bucket contains no non-zero coordinates. (2) w.h.p. 𝑏𝑖 .gamma = 𝛾 (𝑏𝑖 .alpha) if and only if the bucket contains exactly 1 non-zero coordinate. In this case, 𝑏𝑖 .alpha contains the exact index of that coordinate.

10: 11: 12:

Initialize new bucket list 𝐵 ′ with ℓ empty buckets. Copy all non-empty buckets from 𝐵 to 𝐵 ′ . 𝐵 ← 𝐵′

13: function update(𝑢) 14:

For use in our description of BalloonSketch, we define the following additional properties for vector 𝑥 ∈ F𝑛2 with support size 𝑚:

15:

• Bucket States: A bucket 𝑏𝑖 is empty if its support size is 0. It is good if its support size is exactly 1, and bad otherwise. • Bucket Depth: We refer to the index of a bucket as its depth. • Sketch Depth: The smallest index 𝑘 ∈ [𝜌] such that 𝑏𝑖 is empty for all 𝑖 ≥ 𝑘, or 𝜌 if no such 𝑘 exists.

17:

16:

18: 19: 20: 21:

𝑖 ← index of random bucket for 𝑢 (found from ℎ(𝑢)) if 𝑖 ≥ 𝐵.𝑠𝑖𝑧𝑒 () then reallocate(𝑖 + 1) Update bucket 𝐵 [𝑖] with 𝑢. Update bucket 𝐵 [0] with 𝑢. if 𝑖 == 𝐵.𝑠𝑖𝑧𝑒 () − 1 and 𝐵 [𝑖] is empty then 𝑑 ← index of deepest non-empty bucket in 𝐵. if 𝑑 < 𝐵.𝑠𝑖𝑧𝑒 () − 1 then reallocate(𝑑 + 1)

The update function first computes the random bucket index for 𝑢, and if necessary reallocates the bucket list so that there is a bucket allocated at that index. Then both the random bucket and the deterministic bucket are updated. Finally, if the random bucket was the last bucket in the list, and it became empty from this update, the bucket list is reallocated to remove all empty buckets at the tail. This only has to occur if the random bucket was the last bucket, because otherwise there must be a later bucket that is still non-empty. Because of the possible need to reallocate the bucket list during an update and the cost of possibly searching for the deepest non-empty bucket, the time for an update to coordinate 𝑢 can be proportional to the depth of the random bucket for 𝑢. Since this bucket is chosen randomly between index 0 and 𝜌 − 1, the worst-case update time for a BalloonSketch is Θ(log(𝑛)). This is notably worse than CameoSketch’s worst-case update time of Θ(1). For similar reasons, the only worst-case space guarantee for BalloonSketch is Θ(log(𝑛)) which matches CameoSketch but is no better for sparse vectors. However, there are three key observations that give hope for asymptotic space savings and update efficiency for a sketch matrix: (1) The index of the random bucket a coordinate is assigned to is a geometric random variable, and thus has Θ(1) expected value. (2) The residual depth of a sketch is bounded by a geometric random variable and thus has Θ(1) expected value. (3) In a sketch matrix, these random variables for each sketch are independent, and sums of independent random variables concentrate around the sum of their expectations. These observations guide our proof of Theorem 1.3 which provides high probability bounds on the space usage and update time of a BalloonSketch matrix with 𝐿 sketches. When 𝐿 = Θ(log 𝑛) (as is the case for applications like streaming connectivity), The update time for a BalloonSketch matrix is 𝑂 (log 𝑛) w.h.p., whereas the update time for a CameoSketch matrix is 𝑂 (log 𝑛) worst-case. In this case the BalloonSketch uses𝑂 (log 𝑛 log 𝑚) space w.h.p. (where𝑚 is the number of non-zero elements in the vector), whereas CameoSketch uses Θ(log2 𝑛) worst-case space. This indicates that on sparse vectors (low 𝑚) BalloonSketch can use asymptotically less space than CameoSketch. The full proof is provided in Appendix A. Theorem 1.3 (BalloonSketch). There exists an ℓ0 -sampler, BalloonSketch, such that given 𝐿 independent BalloonSketches, each sketching the same vector 𝑥 ∈ F𝑛 with 𝑚 = ∥𝑥 ∥ 0 : (1) The total space usage of the sketches is 𝑂 (𝐿 log 𝑚 + log 𝑛) w.h.p. (2) The total cost of one update to each sketch is 𝑂 (𝐿 + log 𝑛) w.h.p.

3.2

Proof of Theorem 1.2

Our hybrid streaming algorithm generally maintains the adjacency lists of light vertices as an explicit set, and maintains the adjacency lists of heavy vertices as a BalloonSketch matrix with 𝐿 = Θ(log 𝑉 ) and an IBLT with recovery size 𝛿/2. For the explicit set, we will use a standard balanced binary search tree (BBST) data structure. As mentioned previously, we only convert a vertex’s adjacency list from a sketch to an explicit set if its degree becomes ≤ 𝛿/2. This means there may be some light vertices that are stored as a sketch, but their degree is Ω(𝛿). To simplify things, we say a vertex whose adjacency list is stored as a sketch is in sketch form, and we say it is in explicit form otherwise. A vertex in sketch form has 𝑑 (𝑣) = Ω(𝛿) and a vertex in explicit form has 𝑑 (𝑣) = 𝑂 (𝛿).

One additional detail in our algorithm is that for edges with at least one endpoint in explicit form, we will only store the edge in the adjacency list of one of its endpoints: the one that is in explicit form or either endpoint if both are in explicit form. All other edges between two vertices in sketch form are stored by both endpoints. This not only saves a bit of space in practice, but it is a crucial invariant to ensure the success of our connected components query algorithm (described in Appendix B). When analyzing the space usage, we make the simplifying assumption that each vertex stores all of its incident edges, which serves as an upper bound for the true space usage. In the remainder of this section we discuss and analyze the space usage, the update algorithm, and the connected component query algorithm. Together these things compose the proof of Theorem 1.2. Space Usage. For a single vertex of degree 𝑑, a set representation (BBST) requires Θ(𝑑) space. In contrast, the BalloonSketch matrix representation consumes 𝑂 (log 𝑉 log 𝑑) space w.h.p. The optimal density threshold 𝛿, which dictates whether the sketch or the set is more space-efficient, occurs where these two complexities are equal. Solving for𝑑 yields a threshold of 𝛿 = Θ(log 𝑉 log log 𝑉 ). At this density, the space complexity of the BalloonSketch matrix evaluates to 𝑂 (log 𝑉 log(log 𝑉 log log 𝑉 )) = 𝑂 (log 𝑉 log log 𝑉 ) w.h.p. We prove in Appendix D that by setting the density threshold 𝛿 = Θ(log 𝑉 log log 𝑉 ), the total space complexity across all vertices satisfies both 𝑂 (𝑉 + 𝐸) and 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. These bounds collectively establish the space requirements for Theorem 1.1. Stream Updates. First we describe edge updates assuming no promotion or demotion occurs. If we insert or delete an edge (𝑢, 𝑣) and both endpoints are in sketch form, we update the BalloonSketch matrix and IBLT for both endpoints. If either endpoint is in explicit form, the edge should only be stored in the adjacency list of one of the endpoints that is in explicit form. For insertions, we arbitrarily pick one of these endpoints and insert the edge into its set. For deletions, we check both endpoints and delete the edge if the set contains it. When an edge insertion causes a vertex 𝑢 in explicit form to exceed the density threshold (𝑑 (𝑢) > 𝛿), 𝑢 is promoted to sketch form. At this point, 𝑢 converts its set into sketch form by initiating a new BalloonSketch and an IBLT. To maintain the invariant, 𝑢 iterates through the edges currently in its set and redistributes them as follows. For neighbors in sketch form, these edges now exist between two vertices in sketch form. Vertex 𝑢 adds the edge to its new sketch and issues an update to the neighbor 𝑣 instructing it to also add the edge to its sketch. For neighbors in explicit form, these edges now have exactly one endpoint in explicit form (the neighbor). Since the vertex 𝑢 is now in sketch form, it can no longer store these edges. It therefore pushes these edges to the respective neighbors’ sets and does not add them to its own sketch. Conversely, if edge deletions cause a sketch-form vertex 𝑢 to drop to𝑑𝑢 ≤ 𝛿/2, it demotes to explicit form. Because the invariant ensures 𝑢’s IBLT only tracks edges where both endpoints were in sketch form, 𝑢 uses its IBLT to perfectly recover these edges. It moves these recovered edges into its new explicit set and issues updates to those neighbors (which are still in sketch form) to delete the edges from their sketches. Crucially, any edges 𝑢 shares with other explicit form vertices were already uniquely stored in the neighbors’ sets. We prove in Appendix B that updates have amortized cost 𝑂 (log 𝑉 ) w.h.p.

4

Hybrid Fully-Dynamic Connectivity

We prove Theorem 1.1, resulting in a hybrid fully-dynamic graph connectivity algorithm. Theorem 1.1 (Hybrid Dynamic Connectivity). There exists a dynamic connectivity algorithm with space complexity     𝐸 w.h.p. 𝑂 min 𝑉 + 𝐸, 𝑉 log(𝑉 ) log 2 + 𝑉 The update complexity is amortized 𝑂 (log4 𝑉 ). The query complexity is worst-case 𝑂 (log 𝑉 /log log 𝑉 ). The first component of this is a new purely sketch-based dynamic connectivity algorithm with space complexity 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. This results from combining our BalloonSketch techniques described in Section 3 with the sketch-based dynamic connectivity algorithm of Gibb et al. [30] (Gibb’s algorithm). Unlike the streaming algorithm from Section 3, it is not as straightforward to develop a hybrid version of this dynamic algorithm, because the data structures representing the neighborhood of each vertex are not neatly separated: they are heavily intertwined in the cutset data structures which maintain aggregate sketches over several subsets of vertices. Thus we can not simply use a hybrid approach on the granularity of each vertex. Instead, to prove Theorem 1.1 we introduce a novel dynamic connectivity framework which uses different data structures to store the sparse regions and dense regions of the input graph. Employing a hybrid approach over regions of the graph allows us to overcome the difficulty of doing it on the granularity of vertices. Our framework is general, and can use any two dynamic connectivity algorithms (assuming they support a certain reasonable set of operations) to store the sparse and dense regions of the graph. Our framework is intended to use a lossless algorithm to store the sparse regions, and a sketchbased algorithm to store the dense regions. We show that by using our new BalloonSketch-based algorithm as the dense algorithm and using a lossless algorithm with linear space (and low polylogarithmic time updates), such as the Cluster Forest algorithm [21, 59], as the sparse algorithm, Theorem 1.1 is achieved.

4.1

BalloonSketch-Based Dynamic Algorithm

The starting point for new sketch-based algorithm is Gibb’s algorithm [30] (summarized in Section 2.3). Rather than using the ℓ0 sketch algorithm of Cormode et al. [18], we will instead use our new ℓ0 -sketch from Section 3.1, BalloonSketch. Recall that the data structures maintained by Gibb’s algorithm are Θ(log 𝑉 ) levels of cutset data structures (see Section 2.3). Using the sketch of Cormode et al., the space used by each cutset is O (𝑉 log 𝑉 ) w.h.p., resulting in O (𝑉 log2 𝑉 ) space w.h.p. overall. We prove that by using BalloonSketch instead of the sketch of Cormode et al. in the cutset data structures, the aggregate space usage of each cutset data structure can be reduced to O (𝑉 log(𝐸/𝑉 )) in expectation, and the total space usage for the entire algorithm can be reduced to O (𝑉 log(𝑉 ) log(𝐸/𝑉 )) w.h.p. There is inherent flexibility in the specific implementation of the cutset data structure, as any dynamic tree supporting subtree aggregate queries can be used. Previous works such as Gibb’s algorithm and CUPCaKE use Euler-tour trees (ETTs) for this purpose, but the asymptotic space usage is the same regardless of the choice of dynamic

tree. In this work, we implement the cutset data structures using UFO trees [23] augmented with BalloonSketch sketches. We chose to use UFO trees because they simplify the analysis of the total space complexity across all BalloonSketches in our data structures. Our overall dynamic connectivity data structure and algorithms remain equivalent to Gibb’s algorithm. Since UFO trees provide the same update complexity as ETTs, the overall update and query complexity of our dynamic connectivity algorithm remain the same: 𝑂 (log4 𝑉 ) and 𝑂 (log 𝑉 /log log 𝑉 ) respectively. Lemma 4.1 summarizes the results of our algorithm. Lemma 4.1. There exists a dynamic connectivity algorithm with space complexity 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. The update complexity is 𝑂 (log4 𝑉 ). The query complexity is 𝑂 (log 𝑉 /log log 𝑉 ). Space Usage. Here we provide an overview of the space complexity analysis for our new algorithm. We provide the full proof of Lemma 4.1 in Appendix C. In our prior proof of the space usage of our streaming algorithm ( Theorem 1.2, Section 3), we established that the total space usage of the BalloonSketch matrix for each vertex 𝑣 is Θ(log 𝑉 log 𝑑 𝑣 ) w.h.p. Proving the space bounds for our dynamic algorithm introduces two main challenges. First, we must account for space in internal UFO tree nodes, not just the leaves representing the vertices of the graph. While leaf nodes asymptotically dominate the total node count, higher-level internal nodes may sketch an increasing average number of edges. We must rigorously prove that the sum of these potentially larger internal BalloonSketches does not asymptotically exceed the leaf-level space. Second, the Θ(log 𝑉 ) sketches for a vertex are distributed across independent UFO trees. Naively bounding the space of each sketch individually yields a suboptimal 𝑂 (𝑉 log2 𝑉 ) total space w.h.p. Instead, we must leverage the independent random seeds across tiers to aggregate sketch residual depths and apply concentration bounds, achieving the tighter 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) bound w.h.p. Vertex Updates. For use in our hybrid dynamic connectivity algorithm described in the next section, we describe how to modify our new BalloonSketch-based dynamic connectivity algorithm to support a changing set of vertices. Specifically we support the operations InsertVertex(𝑣) and DeleteVertex(𝑣) which insert or delete a degree 0 vertex in the graph. Let 𝑉𝐷 be the current number of vertices in the graph. We assume that there are at most 𝑉 total vertices at any time, that is 𝑉𝐷 ≤ 𝑉 . To maintain that our algorithm is correct w.h.p. in 𝑉 we still maintain Θ(log 𝑉 ) tiers at all times, even if the actual number of vertices 𝑉𝐷 is actually much less than 𝑉 . Consequently, the space usage of the data structure is 𝑂 (𝑉𝐷 log 𝑉 log(2 + 𝐸/𝑉𝐷 )) with high probability in 𝑉 (note that the first logarithmic term is in terms of 𝑉 , not 𝑉𝐷 ). To support vertex updates, we maintain a hash map that maps each vertex 𝑣 to the UFO tree leaf cluster representing them in each tier. Vertex insertions allocate a new UFO cluster with a BalloonSketch in each tier, and vertex deletions free them all. Both take 𝑂 (log 𝑉 ) time, since an empty BalloonSketch has constant size.

4.2

Hybrid Dynamic Connectivity Framework

In this section, we introduce our hybrid dynamic connectivity framework. First we provide a few key definitions. As before, our framework is parametrized by some fixed density threshold 𝛿.

(a) Input Graph

(b) Dense Region

(c) Sparse Region + Spanning Forest

Figure 2: An example of the partitioning of a graph by our hybrid framework with density threshold 𝛿 = 3. Subfigure (a) shows a graph G. The blue vertices and edges in (a) represent heavy vertices and dense edges, and the red vertices and edges represent light vertices and sparse edges. Subfigure (b) shows the dense region of G which is stored by 𝐴𝐿𝐺 𝐷 , indicating the spanning forest with blue edges. Subfigure (c) shows the union of the sparse region of G and the spanning forest from 𝐴𝐿𝐺 𝐷 , which is stored by 𝐴𝐿𝐺𝑆 . • A heavy vertex is defined as a vertex 𝑣 such that 𝑑 (𝑣) ≥ 𝛿. • A light vertex is defined as a vertex 𝑣 such that 𝑑 (𝑣) < 𝛿. • A dense edge is defined as an edge 𝑒 = (𝑢, 𝑣) such that 𝑢 and 𝑣 are both heavy vertices. • A sparse edge is defined as any edge that is not a dense edge. • The dense region of G is the subgraph induced by the heavy vertices. That is all the heavy vertices, and all the dense edges (between two heavy vertices). • The sparse region of G contains all vertices in V and all the sparse edges. Note that by these definitions, the edges of the graph are partitioned between the dense region and sparse region, while there may be overlap in the sets of vertices in each region (the sparse region always has all vertices and the dense region has a subset). Our framework uses two separate dynamic connectivity algorithms to store the dense and sparse regions of the graph: • Dense Algorithm (𝑨𝑳𝑮𝑫 ): stores only the dense region of G. • Sparse Algorithm (𝑨𝑳𝑮𝑺 ): stores the union of the sparse region of G and a spanning forest of the dense region. Specifically, we require that 𝐴𝐿𝐺 𝐷 explicitly stores a spanning forest, and that 𝐴𝐿𝐺𝑆 contains the same spanning forest of the dense region that is maintained by 𝐴𝐿𝐺 𝐷 . This means that all edges are partitioned between 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 except for these dense spanning forest edges which are stored by both algorithms. Figure 2 shows an example of a graph G, its dense and sparse regions, and the subgraphs maintained by 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 . Our framework is designed to use a lossless algorithm using 𝑂 (𝑉 + 𝐸) space as 𝐴𝐿𝐺𝑆 , and a sketch-based algorithm using at most 𝑂 (𝑉 log2 𝑉 ) space as 𝐴𝐿𝐺 𝐷 , however this is not a requirement. Our framework only requires that (in addition to supporting all the operations required by the dynamic connectivity problem) 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 have the following properties, which are standard or easily supported by most existing dynamic connectivity algorithms:

Requirements for 𝐴𝐿𝐺 𝐷 : • Explicitly maintains a spanning forest 𝑨𝑳𝑮𝑫 .F over its graph. Note that some dynamic connectivity algorithms can answer connectivity queries, but do not maintain a spanning forest. • InsertEdge and DeleteEdge operations return a list of the changes to 𝑨𝑳𝑮𝑫 .F induced by the update. • InsertVertex(𝒗)/DeleteVertex(𝒗): Given a vertex𝑣 with 𝑑 (𝑣) = 0, inserts or deletes 𝑣 in the graph. This is necessary since the vertex set in the dense region of the graph may change. Requirements for 𝐴𝐿𝐺𝑆 : • IncidentEdges(𝒗): Return all edges incident to vertex 𝑣. This is not supported by existing sketch-based methods, but is simple for most lossless methods. • 𝒆 ∈ 𝑨𝑳𝑮𝑺 .E: Returns whether edge 𝑒 is in the graph maintained by 𝐴𝐿𝐺𝑆 . This is also not possible for existing sketch-based methods, but easy for lossless methods. Most notably, 𝐴𝐿𝐺 𝐷 require each update to return a list of changes to its spanning forest. We require this because different dynamic connectivity algorithms can vary greatly in how they update their spanning forest in response to edge insertions or deletions. For example, any insertions or deletions in sketch-based algorithms like Gibb’s algorithm can induce up to Θ(log 𝑉 ) spanning forest changes. In addition to 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 , our framework stores a few extra data structures to interface between the two. To handle vertices that change from heavy to light, our framework maintains an IBLT with recovery size 𝛿/2, for each vertex in 𝐴𝐿𝐺 𝐷 . We also store an array of 𝑉 boolean values indicating whether each vertex is in 𝐴𝐿𝐺 𝐷 . The last piece of additional data stored by our framework is the global degree 𝑑 (𝑣) for each vertex 𝑣 (its degree in the input graph G). This is necessary because the edges of G may be divided between 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 and some edges may be in both, so it is hard to discern the total degree using just these data structures. In the remainder of this section we abstractly describe the query and update algorithms for our hybrid framework in terms of 𝐴𝐿𝐺𝑆

and 𝐴𝐿𝐺 𝐷 . In the next section (Section 4.3) we analyze the theoretical guarantees provided by our framework when using the Cluster Forest algorithm [59] as 𝐴𝐿𝐺𝑆 , and the BalloonSketch-based algorithm from Section 4.1 as 𝐴𝐿𝐺 𝐷 . Query Algorithm. Since 𝐴𝐿𝐺𝑆 stores the union of the sparse region of the graph and a spanning forest of the dense region, all vertices in G are in 𝐴𝐿𝐺𝑆 , and the connected components in 𝐴𝐿𝐺𝑆 are exactly the same as the connected components of G. Thus, a query Connected(𝑢, 𝑣) in our framework can be answered at any time by calling 𝐴𝐿𝐺𝑆 .Connected(𝑢, 𝑣).

Algorithm 3 Edge deletion algorithms for the hybrid framework. 1: function DeleteEdge(𝑒 = {𝑢, 𝑣 }) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

Algorithm 2 Edge insertion algorithms for the hybrid framework. 1: function InsertEdge(𝑒 = {𝑢, 𝑣 }) 2: 3: 4: 5: 6: 7: 8: 9: 10: 11:

for 𝑥 ∈ {𝑢, 𝑣 } do 𝑑 (𝑥) ← 𝑑 (𝑥) + 1 if 𝑥 ∉ 𝐴𝐿𝐺 𝐷 .V and 𝑑 (𝑥) > 𝛿 then PromoteVertex(𝑥) if 𝑢 ∈ 𝐴𝐿𝐺 𝐷 .V and 𝑣 ∈ 𝐴𝐿𝐺 𝐷 .V then 𝐴𝐿𝐺 𝐷 .InsertEdge(𝑒) IBLT𝑢 .Insert(𝑣), IBLT𝑣 .Insert(𝑢) Update 𝐴𝐿𝐺𝑆 with all changes to 𝐴𝐿𝐺 𝐷 .F . else 𝐴𝐿𝐺𝑆 .InsertEdge(𝑒)

for 𝑥 ∈ {𝑢, 𝑣 } do 𝑑 (𝑥) ← 𝑑 (𝑥) − 1 if 𝑥 ∈ 𝐴𝐿𝐺 𝐷 .V and 𝑑 (𝑥) ≤ 𝛿/2 then DemoteVertex(𝑥) if 𝑢 ∈ 𝐴𝐿𝐺 𝐷 .V and 𝑣 ∈ 𝐴𝐿𝐺 𝐷 .V then 𝐴𝐿𝐺 𝐷 .DeleteEdge(𝑒) IBLT𝑢 .Delete(𝑣), IBLT𝑣 .Delete(𝑢) Update 𝐴𝐿𝐺𝑆 with all changes to 𝐴𝐿𝐺 𝐷 .F . else 𝐴𝐿𝐺𝑆 .DeleteEdge(𝑒)

12: function DemoteVertex(𝑣) 13: 14: 15: 16: 17: 18: 19: 20:

for 𝑒 = (𝑢, 𝑣) ∈ IBLT𝑣 .Recover() do 𝐴𝐿𝐺 𝐷 .DeleteEdge(𝑒) IBLT𝑢 .Delete(𝑣) if 𝑒 ∉ 𝐴𝐿𝐺𝑆 .E then 𝐴𝐿𝐺𝑆 .InsertEdge(𝑒) Update 𝐴𝐿𝐺𝑆 with all changes to 𝐴𝐿𝐺 𝐷 .F . 𝐴𝐿𝐺 𝐷 .DeleteVertex(𝑣) Delete IBLT𝑣

12: function PromoteVertex(𝑣) 13: 14: 15: 16: 17: 18: 19: 20:

𝐴𝐿𝐺 𝐷 .InsertVertex(𝑣) Instantiate IBLT𝑣 for 𝑒 = {𝑣, 𝑢} ∈ 𝐴𝐿𝐺𝑆 .IncidentEdges(𝑣) do if 𝑢 ∈ 𝐴𝐿𝐺 𝐷 .V then 𝐴𝐿𝐺 𝐷 .InsertEdge(𝑒) IBLT𝑢 .Insert(𝑣), IBLT𝑣 .Insert(𝑢) 𝐴𝐿𝐺𝑆 .DeleteEdge(𝑒) Update 𝐴𝐿𝐺𝑆 with all changes to 𝐴𝐿𝐺 𝐷 .F .

Insertion Algorithm. Algorithm 2 shows the pseudo-code for inserting an edge 𝑒 = {𝑢, 𝑣 } in our hybrid framework. First, the algorithm updates the global degree of 𝑢 and 𝑣, and if their new degree is > 𝛿, calls PromoteVertex on them (lines 2–5). PromoteVertex(𝑣) first inserts 𝑣 into 𝐴𝐿𝐺 𝐷 and instantiates an IBLT for 𝑣 (lines 13–14). Next, for all the edges incident to 𝑣 in 𝐴𝐿𝐺𝑆 , if the other endpoint is also in 𝐴𝐿𝐺 𝐷 they are inserted into 𝐴𝐿𝐺 𝐷 and the IBLTs, and deleted from 𝐴𝐿𝐺𝑆 (lines 15–19). This ensures that 𝐴𝐿𝐺 𝐷 includes all edges that became dense edges when 𝑣 became a heavy vertex. Finally, we must update 𝐴𝐿𝐺𝑆 to contain the spanning forest maintained by 𝐴𝐿𝐺 𝐷 . As mentioned previously, our framework requires that edge insertion operations in 𝐴𝐿𝐺 𝐷 report a list of changes to the spanning forest caused by these insertions. Our algorithm uses this list of changes to insert or delete any necessary edges in 𝐴𝐿𝐺𝑆 so that it always stores the exact spanning forest maintained by 𝐴𝐿𝐺 𝐷 . Now that the algorithm has dealt with vertices becoming heavy, the next step is to actually insert the new edge 𝑒. If both endpoints of 𝑒 are in the dense region, we insert 𝑒 into 𝐴𝐿𝐺 𝐷 , update the IBLTs for both endpoints, and again update 𝐴𝐿𝐺𝑆 with all the spanning forest changes in 𝐴𝐿𝐺 𝐷 (lines 6–9). Else we simply insert 𝑒 into 𝐴𝐿𝐺𝑆 , since the edge is in the sparse region of the graph (line 11).

Deletion Algorithm. Algorithm 3 shows the pseudo-code for deleting an edge 𝑒 = {𝑢, 𝑣 } in our hybrid framework. First, the algorithm updates the global degree of 𝑢 and 𝑣, and if their new degree is ≤ 𝛿/2, calls DemoteVertex on them (lines 2–5). Similar to our hybrid streaming algorithm (Section 3), we only demote vertices when their degree drops down to 𝛿/2 to prevent thrashing and enable efficient amortized update complexity. DemoteVertex(𝑣) uses the IBLT of 𝑣 to extract the at most 𝛿/2 edges incident to 𝑣 in 𝐴𝐿𝐺 𝐷 (line 13). For each of these edges, they are deleted from 𝐴𝐿𝐺 𝐷 , deleted from the IBLT of the other endpoint, and inserted into 𝐴𝐿𝐺𝑆 if they are not already present there (lines 14–17). Once again, any changes caused to the spanning forest maintained by 𝐴𝐿𝐺 𝐷 by these deletions must be updated in 𝐴𝐿𝐺𝑆 . In particular, this step must avoid deleting the edges just inserted to 𝐴𝐿𝐺𝑆 in the previous loop. Finally, 𝑣 is deleted from 𝐴𝐿𝐺 𝐷 , and IBLT𝑣 is freed (lines 19–20). Now the algorithm deletes edge 𝑒. If both endpoints of 𝑒 are in the dense region, delete 𝑒 from 𝐴𝐿𝐺 𝐷 , update the IBLTs for both endpoints, and again update 𝐴𝐿𝐺𝑆 with all the spanning forest changes in 𝐴𝐿𝐺 𝐷 (lines 6–9). This last step is particularly important, because if a spanning forest edge was deleted in 𝐴𝐿𝐺 𝐷 , this edge would currently be present in 𝐴𝐿𝐺𝑆 , and this step also deletes it there (disconnecting the graph represented by 𝐴𝐿𝐺𝑆 ). If a replacement edge was found in 𝐴𝐿𝐺 𝐷 , it becomes part of the spanning forest and is also inserted into 𝐴𝐿𝐺𝑆 . If both endpoints of 𝑒 are not in the dense region, we simply delete 𝑒 from 𝐴𝐿𝐺𝑆 , since the edge is only in the sparse region of the graph (line 11).

4.3

Proof of Theorem 1.1

We prove Theorem 1.1 by analyzing the performance of our hybrid framework using our BalloonSketch-based algorithm from Section 4.1 as 𝐴𝐿𝐺 𝐷 , and the Cluster Forest algorithm [59] as 𝐴𝐿𝐺𝑆 . It is

easily verifiable that our BalloonSketch-based algorithm and Cluster Forest meet the requirements for 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 respectively. We configure the density threshold to be 𝛿 = log 𝑉 log log 𝑉 . Intuitively, this is the value of 𝛿 where if every vertex has degree exactly 𝛿, then the space usage of a lossless representation is asymptotically equal to the space usage required in our BalloonSketch-based algorithm: 𝑂 (𝑉 + 𝑉 𝛿) versus 𝑂 (𝑉 log 𝑉 log(2 + 𝛿𝑉 /𝑉 )). We prove that the space complexity of our algorithm is 𝑂 (𝑉 + 𝐸) w.h.p. and 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p in Appendix D. The key observation for the first bound is that the space used by 𝐴𝐿𝐺 𝐷 is 𝑂 (𝐸) since the existence of 𝑉𝐷 vertices in 𝐴𝐿𝐺 𝐷 implies the total number of edges 𝐸 is at least𝑉𝐷 𝛿. The key observation for the second bound is that 𝐴𝐿𝐺𝑆 uses 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) space since every light vertex has maximum degree 𝛿, so the number of sparse edges is 𝑂 (𝑉 𝛿). We also prove in Appendix D that the update and query complexities are amortized 𝑂 (log4 𝑉 ) and 𝑂 (log 𝑉 /log log 𝑉 ).

5

A final parameter is the number of tiers used in BalloonDC, which must be Θ(log 𝑉 ) in theory. The number of tiers impacts the error rate of the Monte Carlo algorithm. We use ⌈log2 𝑉 ⌉ tiers, which is slightly more aggressive than prior work on graph-sketching methods [56] and below the number of tiers needed according to a standard analysis of the semi-streaming algorithm [3]. We experimentally verify that HybridSCALE actually uses only 64% of these ⌈log2 𝑉 ⌉ tiers (geometric mean across all tested datasets.) We further note that HybridSCALE consistently uses fewer tiers than CUPCaKE. This is intuitively because our design choice to sketch only the dense regions of the graph makes finding connectivity via Borůvka take significantly fewer rounds. Additionally, while we provision enough tiers for the maximum number of vertices, the actual number of vertices present in the dense region is often much lower, naturally reducing the required number of tiers. Together, these factors indicate that there may be an opportunity for more aggressive space savings by reducing the number of tiers stored.

System Design / Implementation 5.1

In this section, we describe HybridSCALE (Hybrid Sketching Connectivity Algorithm with Lossless Edges), our hybrid sketching system for dynamic connectivity based on the algorithm from Section 4. As per the name, our system can seamlessly scale existing dynamic connectivity systems to larger and denser real-world graphs. HybridSCALE consists of three major components: (1) 𝐴𝐿𝐺𝑆 : the Cluster Forest implementation of De Man et al. [21]. (2) 𝐴𝐿𝐺 𝐷 : BalloonDC, an implementation of our new BalloonSketch-based dynamic connectivity algorithm from Section 4.1. (3) A hybrid interface that manages communication and movement of edges and vertices between the first two components. We chose to use this implementation of the Cluster Forest because it provides good guarantees on performance and provides robust stateof-art performance regardless of the structure of the input graph. However, the first two components can be easily interchanged with any other existing or future dynamic connectivity systems that meet the basic requirements for 𝐴𝐿𝐺𝑆 and 𝐴𝐿𝐺 𝐷 . All of our implementations are written in C++ and compiled with -03 optimization. Parameter Configuration. A key parameter in our hybrid algorithm is the density threshold 𝛿. To achieve good theoretical bounds 𝛿 must be Θ(log 𝑉 log log 𝑉 ). In HybridSCALE, we set 𝛿 = 25 · ⌈log2 𝑉 ⌉. We chose this threshold because we experimentally found it to be roughly the best value in terms of minimizing the total memory usage. Conceptually, the constant multiple of 25 ≈ 6 · 4 can be derived from the fact that log log 𝑉 is at most 6 for all of our inputs, and the space usage of a single sketch bucket is 4 times that of storing a neighbor entry in a lossless neighbor array. In HybridSCALE, we demote a vertex when its degree drops to𝛿/8 (as opposed to 𝛿/2 in our theoretical analysis). This choice manages a tradeoff between the aggressiveness of vertex reclamation and global memory overhead. While a higher threshold would move vertices back to the space-efficient Cluster Forest sooner, it would also require every vertex in the dense subsystem to maintain a larger IBLT. Provisioning each IBLT for 𝛿/2 would cause these structures to occupy a significantly larger portion of the system’s total memory. By lowering the threshold to 𝛿/8, we decrease this memory overhead, at the cost of some vertices remaining in the dense subsystem a bit longer.

BalloonDC

BalloonDC uses the implementation of CUPCaKE [22] as a starting point, but makes many modifications. The dynamic tree and ℓ0 -sketching primitives we use are both different than that of CUPCaKE, we handle insertion/deletion of vertices which CUPCaKE does not support, and we improve the buffering techniques of CUPCaKE. Cutset Implementation. Systems like CUPCaKE and BalloonDC rely on multiple tiers of cutset data structures (see Section 2.3 for details). In BalloonDC, we implement the cutset data structure using link-cut trees [53] based on splay trees [54]. Note that our theoretical analysis uses UFO trees [23] to implement the cutset data structure for simplicity of analysis, but in practice we use link-cut trees for their lower empirical memory footprint. Each vertex in the link-cut tree is augmented with a BalloonSketch, which we develop a new implementation for. Link-cut trees typically do not support subtree queries, but they work well for subtree queries in our use-case since sketch addition is an invertible function, and they only need to store one sketch per vertex (avoiding internal aggregate sketches). Additionally, we optimize sketch update operations in the link-cut trees by only splaying an accessed node if its depth exceeds some constant times log 𝑉 . Improved Batching. The CUPCaKE system was optimized to rapidly process batches of updates that induce no structural changes in its cutsets. To take advantage of this, they speculatively buffer batches of updates in hopes that the entire batch will induce no structural changes. This has two major drawbacks. The first is that if the batch of updates does induce a structural update, the system must undo some of the work it did and process each update in the batch oneby-one without the batch optimizations. The second issue is that the update buffer must be flushed whenever a query occurs, so this optimization can be entirely ineffective in streams with many queries, and it can significantly increase query latencies. BalloonDC improves the buffering techniques of CUPCaKE so that any type of updates can be processed in a batch, including ones that induce structural changes. This overcomes the first drawback of CUPCaKE’s buffering strategy. Regarding the second drawback, our HybridSCALE uses Cluster Forest to answer queries, so flushing the update buffer immediately in BalloonDC is not required for queries. The only thing that requires flushing the buffer of updates

is a deletion of a current spanning forest edge in BalloonDC, which happens infrequently, and does not impact query latency.

5.2

Hybrid Interface

The hybrid interface manages communication and movement of edges and vertices between the Cluster Forest and BalloonDC systems, implementing the abstract logic of the algorithm from Section 4. The set of currently dense vertices is stored in a hash table, and the total degree of each vertex is stored as an integer. The hybrid interface also stores an IBLT for each vertex 𝑣 that allows for recovering all of the edges incident to a vertex being demoted from the dense region (see next paragraph for implementation details). To optimize communication, edges that should be moved to the dense subsystem are collected in an update buffer rather than being sent immediately. This buffer is flushed to the dense subsystem in batches either when it reaches capacity or when an incoming update deletes an active edge from the dense spanning forest. Finally, the hybrid interface stores a list of modifications made to the spanning forest during BalloonDC updates. We appropriately append to this list while processing updates in BalloonDC, and apply all these changes to the Cluster Forest after finishing the updates. Recovery IBLTs. Our IBLT implementation is based on the original IBLT algorithm [31] and uses CameoSketch buckets as a building block. Our specific implementation utilizes two tiers of IBLTs with 𝑘 = 3 hash locations and 1.3𝛿/8 buckets and max{log2 𝑉 , 0.2𝛿/8} buckets respectively for the two tiers, using xxHash [17] with iterated seeds to ensure unique hash mapping. Although the original IBLT algorithm’s recovery is only correct w.h.p. in 𝛿 (not in 𝑉 ), we found that the IBLT recovery succeeded in 99.9% of cases in practice. To ensure correctness of our overall system, any failed recovery operation simply aborts the demotion, retaining the vertex in the dense subsystem until a later demotion attempt. While this approach may keep light vertices in the dense subsystem longer, the exceptionally low error rate ensures that any resulting overhead in space or time executing demotions remains negligible.

6

Experiments

Each experiment reported in this section consists of running HybridSCALE on an input stream comprised of edge insertions and deletions generated from some static graph (by inserting all the edges then deleting the set of inserted edges). All experiments were run on a 48-core AMD EPYC 7643 CPU with 256GB of RAM. Datasets. Table 1 summarizes the datasets used in our experiments. The social, web, and road graphs are sourced from SuiteSparse [20] and NetworkRepository [49], and are widely used in academic research. The kron graphs are synthetic Kronecker random graphs generated according to the Graph500 specification [7]. They are studied in all prior graph sketching experimental research because they are dense and exhibit structural properties of real-world networks. The 𝑘nn/rs graphs are symmetrized 𝑘-nearest neighbors (𝑘nn) and range search (rs) graphs over a 1M-point subset of the SIFT1B and MSSPACEV1B datasets from BIGANN [52]. We generate these graphs using ParlayANN [62] to compute the ground truth 𝑘nn or rs. For 𝑘nn graphs, we use 𝑘 = 500. For rs graphs we used a squared euclidean distance radius of 50K and 10K respectively for SIFT1B and

Graph

Type

𝑉

𝐸

2𝐸/𝑉

Max. 𝑘-Core

Cite

Google+ Friendster Twitter Orkut

social social social social

108K 65.6M 41.7M 3.07M

10.8M 1.81B 1.2B 117M

201 55.1 57.7 76.3

676 304 2488 253

[41] [61] [40] [43]

ENWiki Youtube

web web

4.21M 1.16M

91.9M 2.99M

43.7 5.16

145 51

[10] [43]

RoadUSA RoadGermany

road road

23.9M 12.3M

28.9M 16.1M

2.41 2.63

3 3

[48] [48]

SIFT-RS50K SIFT-KNN500 MSSP-RS10K MSSP-KNN500

knn/rs knn/rs knn/rs knn/rs

1M 1M 1M 1M

227M 411M 547M 380M

454 821 1090 760

4301 499 18778 499

[52] [52] [52] [52]

Kron-13 Kron-15 Kron-16

kron kron kron

8.19K 32.8K 65.5K

16.7M 267M 1.07B

4070 16300 32700

2827 11306 22623

[7] [7] [7]

Table 1: Summary of the graph datasets in our experiments.

MSSPACEV1B. The choice of 𝑘 or the search radius when constructing𝑘nn/rs graphs directly controls graph density and is a central modeling question in large-scale graph construction pipelines [13, 24, 62]. Larger values of 𝑘 or radius yield denser graphs with richer connectivity, which typically improves the quality of downstream tasks such as graph-based clustering, semi-supervised learning, and retrieval, but substantially increases storage and processing costs. Smaller values yield sparser graphs that are cheaper to process but can under-connect the underlying data [13]. Because of this trade-off, practitioners building 𝑘nn/rs graphs must target a range of densities depending on the application, which motivates evaluating HybridSCALE across moderately large 𝑘 and radius regimes. Importantly, our list of datasets includes graphs with similar average densities but very different dense cores (see 𝑘-core column in Table 1 which reports the largest 𝑘 such that the graph has a non-empty 𝑘-core). The 𝑘-core of a graph is a popular metric for identifying wellconnected communities within a graph; in particular, all vertices in a 𝑘-core have induced degree (i.e., degree restricted only within this subgraph) at least𝑘. Thus, the presence of a large𝑘-core in a graph implies the existence of a subgraph where all vertices have high degree (in particular, the average degree is at least 𝑘). The social network and road graphs both have relatively low average densities, but the social networks have much larger, denser cores than the road networks. Similarly, for the rs and 𝑘nn graphs, average degrees are similar but the rs graphs have larger, denser cores. This allows us to measure the impact of core size and density on our system performance. Comparison Systems. In these experiments we evaluate the performance of Cluster Forest and CUPCaKE, since they are state-of-the-art implementations of dynamic connectivity systems optimized for sparse and dense graphs respectively. Our focus on these specific systems is intended to demonstrate the efficacy of the hybrid framework. Because the framework is modular, HybridSCALE is designed so that any other sparse or dense optimized implementations developed in the future can be seamlessly integrated.

HybridSCALE

Cluster Forest

CUPCaKE

OOM

Memory

102 101 100 GOOG FRND TWIT ORKT

EN WIKI

YT

ROAD ROAD USA GER

SIFT RS

SIFT KNN

MSSP MSSP KRON KRON KRON RS KNN 13 15 16

Figure 3: Peak memory usage of HybridSCALE, Cluster Forest, and CUPCaKE on various input graph streams (normalized to HybridSCALE). A bar with diagonal hashes indicates that the machine ran out of memory (OOM) while processing that input.

Update Time

HybridSCALE

Cluster Forest

CUPCaKE

CUPCaKE OOM

YT

SIFT RS

MSSP MSSP KRON KRON KRON RS KNN 13 15 16

101 100 GOOG FRND TWIT ORKT

EN WIKI

ROAD ROAD USA GER

SIFT KNN

Figure 4: The total time taken by HybridSCALE, Cluster Forest, and CUPCaKE to process all updates for various input graph streams (normalized to HybridSCALE). The blue × indicates that CUPCaKE ran out of memory (OOM) during initialization.

Memory (B)

1011

HybridSCALE

Cluster Forest

CUPCaKE

1010 109 108 1 2

22

23

25 27 24 26 28 Average Degree (2|E|/|V|)

29

210

Figure 5: Memory usage HybridSCALE, Cluster Forest, and CUPCaKE across various range search graphs constructed from a 1M-point subset of SIFT1B. The search radii are square Euclidean distances 10K, 20K, 30K, 40K, 50K, and 60K.

6.1

Memory Usage Results

For each dataset, we measure the maximum space used by each system at any point during stream ingestion. The results of this experiment are summarized in Figure 3. For each of the (sparse) social, web, and road graphs, the space used by HybridSCALE is comparable to that of the Cluster Forest, and CUPCaKE uses one to two orders of magnitude more space. HybridSCALE is 1.18× more compact than Cluster Forest on the Google+ graph and 1.16× more compact on the Twitter graph, because these graphs have high max 𝑘-core, indicating relatively large, dense cores. The other social, web, and

road graphs have smaller dense cores, leaving fewer opportunities to reduce the space cost by sketching. Consequently HybridSCALE uses slightly more space than Cluster Forest due to the minor space overhead of our hybrid interface. On the (dense) kron graphs, HybridSCALE uses 1–2 orders of magnitude less space than Cluster Forest, because these graphs have very large average degree, making a lossless representation very large. Note that HybridSCALE is also several times smaller than CUPCaKE, primarily due to the space improvements of BalloonSketch, and the usage of link-cut trees instead of Euler-tour trees. On the SIFT1B and MSSPACEV1B datasets, we can further see the importance of core size and density to HybridSCALE’s space performance. On these graphs with 𝑉 = 106 , 𝛿, the HybridSCALE density threshold is 25 · ⌈log2 (106 )⌉ = 500. In the 𝑘nn graphs with 𝑘 = 500 each vertex has degree at least 500, therefore every vertex is included in the dense subsystem. However due to the properties of 𝑘nn graphs, the max 𝑘-core is only 499. Thus these 𝑘nn graphs represent a sort of worst-case input for the hybrid framework where every vertex is just dense enough to be sketched, but the dense region does not have a high enough average degree to achieve meaningful space savings through sketching. In contrast, the rs graphs have no limit on the degree of any vertex and tend to have larger, denser cores than their 𝑘nn counterparts with similar average degree. This core size discrepancy directly affects the space performance of HybridSCALE. For the rs graphs, HybridSCALE is significantly more space-efficient than Cluster Forest. Specifically, for SIFT1B HybridSCALE uses a third of the space of Cluster Forest, and for MSSPACEV1B it uses an order of magnitude less space. For the 𝑘nn

graphs we observe that HybridSCALE is moderately larger than Cluster Forest. Since it cannot save much space by sketching the nonexistent core, its overheads for the sketching and hybrid driver data structures make it a bit larger than Cluster Forest. Density Sweep. Figure 5 further demonstrates the impact of core size, measuring the space usage of each system across rs graphs over the SIFT1B dataset with increasing squared euclidean distance radii. At low radius values, the dense core is too small to sketch efficiently and therefore HybridSCALE and the Cluster Forest are essentially the same size. As the radius (and the size of the dense core) increases, HybridSCALE becomes more compact than Cluster Forest. Note also that regardless of core size, HybridSCALE is significantly smaller than CUPCaKE due to the reduced space complexity of BalloonSketch. Due to this fact, HybridSCALE can effectively leverage sketching to yield space savings at much lower average degrees than CUPCaKE (for CUPCaKE it must be in the low thousands).

6.2

Update Throughput Results

For each dataset, we measured the total time of each system to process all updates in the stream. The results are summarized in Figure 4. Our goal is to show that our hybrid framework incurs no significant degradation over the running time of its two subsystems. For example, on sparser graphs where few edges are sketched (e.g. the road graphs) the performance of HybridSCALE is essentially the same as that of cluster forest. On the other hand, on graphs where most of the edges are sketched, (e.g. the 𝑘nn and kron graphs), the update performance of HybridSCALE is closer to that of CUPCaKE. For sparse graphs with reasonably dense cores (social and rs graphs), both subsystems of HybridSCALE process a significant fraction of the edges, thus the running time is between Cluster Forest and CUPCaKE.

7

Conclusion

This work advances the story of practical graph sketching in several important ways. Sketch-based dynamic graph algorithms have a very different space usage profile from lossless ones: their space scales with the number of vertices rather than the number of edges, which is extremely attractive on dense graphs but imposes a significant pervertex overhead that makes them very costly on sparse real-world graphs. This mismatch between where sketching shines in theory and where graphs actually sit in practice has long stood in the way of the broader adoption of graph sketching. Our central message of this paper is that sketching does not need to win on every graph in order to be useful. In particular, by applying sketching selectively to the dense cores of graphs and storing the rest losslessly, hybrid sketching can leverage sketching exactly where it helps most. Hybrid sketching is thus a simple “self-tuning” data structure that works well on graphs with densities ranging from very sparse graphs all the way toward very dense regimes where sketching offers massive advantages. Hybrid sketching is a general approach, not a single algorithm. In particular, our system HybridSCALE is agnostic to the specific lossless and sketch-based subroutines it wraps, so future work can freely substitute new components as the underlying algorithms improve. For instance, we could replace the lossless subsystem with a heuristic structure such as the ID-Tree [60], which trades theoretical guarantees for fast empirical performance on low-diameter graphs, or plug in future improved sketching primitives. Hybrid sketching should

also be naturally applicable to other graph streaming problems such as cut and spectral sparsifiers, spanners, triangle counting, and other sketch-based dynamic graph data structures. The broader takeaway of our work is that when used carefully, graph sketching already provides meaningful space savings for real-world graph datasets.

Acknowledgments We gratefully acknowledge support from NSF grants CCF-2247577, CCF-2403235, CNS-2317194, and NRT-HDR 2125295.

References [1] Umut A. Acar, Daniel Anderson, Guy E. Blelloch, and Laxman Dhulipala. 2019. Parallel Batch-Dynamic Graph Connectivity. In Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 381–392. https://doi.org/10.1145/3323165.3323196 [2] Umut A. Acar, Daniel Anderson, Guy E. Blelloch, Laxman Dhulipala, and Sam Westrick. 2020. Parallel Batch-Dynamic Trees via Change Propagation. In 28th Annual European Symposium on Algorithms (ESA). 2:1–2:23. https://doi.org/10.4230/LIPIcs.ESA.2020.2 [3] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Analyzing graph structure via linear measurements. In Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms. SIAM, 459–467. [4] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. 2012. Graph sketches: sparsification, spanners, and subgraphs. In PODS. ACM, 5–14. [5] Noga Alon, Yossi Matias, and Mario Szegedy. 1999. The Space Complexity of Approximating the Frequency Moments. J. Comput. System Sci. 58, 1 (1999), 137–147. https://doi.org/10.1006/jcss.1997.1545 [6] J. Ignacio Alvarez-Hamelin, Luca Dall’Asta, Alain Barrat, and Alessandro Vespignani. 2005. Large Scale Networks Fingerprinting and Visualization Using the 𝑘 -Core Decomposition. In Advances in Neural Information Processing Systems (NeurIPS). 41–50. [7] James A. Ang, Brian W. Barrett, Kyle B. Wheeler, and Richard C. Murphy. 2010. Introducing the Graph 500. In Cray User Group (CUG) Proceedings. https://cug.org/5-publications/proceedings_attendee_lists/CUG10CD/pages/1program/final_program/CUG10_Proceedings/pages/authors/11-15Wednesday/ 14C-Murphy-paper.pdf [8] Vladimir Batagelj and Matjaž Zaveršnik. 2003. An 𝑂 (𝑚) Algorithm for Cores Decomposition of Networks. arXiv preprint cs/0310049 (2003). [9] Djamal Belazzougui, Gregory Kucherov, and Stefan Walzer. 2024. Better Space-Time-Robustness Trade-Offs for Set Reconciliation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 297), Karl Bringmann, Martin Grohe, Gabriele Puppis, and Ola Svensson (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 20:1–20:19. https://doi.org/10.4230/LIPIcs.ICALP.2024.20 [10] Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph Framework I: Compression Techniques. In Proceedings of the 13th International Conference on World Wide Web (WWW). ACM, 595–602. https://doi.org/10.1145/988672.988752 [11] Stephen P. Borgatti and Martin G. Everett. 2000. Models of Core/Periphery Structures. Social Networks 21, 4 (2000), 375–395. https://doi.org/10.1016/S03788733(99)00019-2 [12] Daniel G. Brown. 2011. How I Wasted Too Long Finding a Concentration Inequality for Sums of Geometric Variables. (2011). [13] CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren Schudy, and Peilin Zhong. 2022. Stars: Tera-Scale Graph Building for Clustering and Learning. In Advances in Neural Information Processing Systems (NeurIPS). [14] Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. 2007. A Model of Internet Topology Using 𝑘 -Shell Decomposition. Proceedings of the National Academy of Sciences (PNAS) 104, 27 (2007), 11150–11154. https://doi.org/10.1073/pnas.0701175104 [15] Moses Charikar, Kevin Chen, and Martin Farach-Colton. [n. d.]. Finding Frequent Items in Data Streams. ([n. d.]). [16] Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. 2020. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond. In 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS). 1158–1167. https://doi.org/10.1109/FOCS46700.2020.00111 [17] Yann Collet. 2016. xxHash-Extremely fast non-cryptographic hash algorithm. URL https://github. com/Cyan4973/xxHash (2016). [18] Graham Cormode and Donatella Firmani. 2014. A unifying framework for l0-sampling algorithms. Distrib. Parallel Databases 32, 3 (sep 2014), 315–335. https://doi.org/10.1007/s10619-013-7131-9

[19] Graham Cormode and Shanmugavelayutham Muthukrishnan. 2005. An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. Journal of Algorithms 55, 1 (2005), 58–75. https://doi.org/10.1016/j.jalgor.2003.12.001 [20] Timothy A. Davis and Yifan Hu. 2011. The university of Florida sparse matrix collection. ACM Trans. Math. Softw. 38, 1, Article 1 (dec 2011), 25 pages. https://doi.org/10.1145/2049662.2049663 [21] Quinten De Man, Laxman Dhulipala, Adam Karczmarz, Jakub Łącki, Julian Shun, and Zhongqi Wang. 2024. Towards Scalable and Practical BatchDynamic Connectivity. Proc. VLDB Endow. 18, 3 (Nov. 2024), 889–901. https://doi.org/10.14778/3712221.3712250 [22] Quinten De Man, Qamber Jafri, Daniel Delayo, Evan T. West, Michael A. Bender, and David Tench. 2025. Fast and Compact Sketch-Based Dynamic Connectivity. arXiv:2509.14433 [cs.DS] https://arxiv.org/abs/2509.14433 [23] Quinten De Man, Atharva Sharma, Kishen N Gowda, and Laxman Dhulipala. 2026. UFO Trees: Practical and Provably-Efficient Parallel Batch-Dynamic Trees. In Proceedings of the 31st ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (Sydney, NSW, Australia) (PPoPP ’26). Association for Computing Machinery, New York, NY, USA, 109–122. https://doi.org/10.1145/3774934.3786431 [24] Wei Dong, Moses Charikar, and Kai Li. 2011. Efficient k-nearest neighbor graph construction for generic similarity measures. In Proceedings of the 20th International Conference on World Wide Web (WWW). [25] Pavlos S. Efraimidis and Paul G. Spirakis. 2006. Weighted Random Sampling with a Reservoir. Inform. Process. Lett. 97, 5 (2006), 181–185. https://doi.org/10.1016/j.ipl.2005.11.003 [26] David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. 1997. Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms. J. ACM 44, 5 (1997), 669–696. https://doi.org/10.1145/265910.265914 [27] Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. 1999. On Power-Law Relationships of the Internet Topology. ACM SIGCOMM Computer Communication Review 29, 4 (1999), 251–262. https://doi.org/10.1145/316194.316229 [28] Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. 2005. On Graph Problems in a Semi-Streaming Model. Theor. Comput. Sci. 348, 2 (Dec. 2005), 207–216. https://doi.org/10.1016/j.tcs.2005.09.013 [29] Greg N. Frederickson. 1985. Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications. SIAM J. Comput. 14, 4 (1985), 781–798. https://doi.org/10.1137/0214055 [30] David Gibb, Bruce Kapron, Valerie King, and Nolan Thorn. 2015. Dynamic graph connectivity with improved worst case update time and sublinear space. arXiv:1509.06464 [cs.DS] [31] Michael T Goodrich and Michael Mitzenmacher. 2011. Invertible bloom lookup tables. In 2011 49th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 792–799. [32] Monika R. Henzinger and Valerie King. 1999. Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation. J. ACM 46, 4 (1999), 502–516. https://doi.org/10.1145/320211.320215 [33] Monika R. Henzinger and Mikkel Thorup. 1997. Sampling to Provide or to Bound: With Applications to Fully Dynamic Graph Algorithms. Random Structures & Algorithms 11, 4 (1997), 369–379. https://doi.org/10.1002/(SICI)10982418(199712)11:4<369::AID-RSA5>3.0.CO;2-V Poly[34] Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. 2001. Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. J. ACM 48, 4 (2001), 723–760. https://doi.org/10.1145/502090.502095 [35] Jacob Holm, Eva Rotenberg, and Mikkel Thorup. 2018. Dynamic BridgeFinding in 𝑂˜ (log2 𝑛) Amortized Time. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 35–52. https://doi.org/10.1137/1.9781611975031.3 [36] Shang-En Huang, Dawei Huang, Tsvi Kopelowitz, Seth Pettie, and Mikkel Thorup. 2023. Fully Dynamic Connectivity in 𝑂 (log 𝑛 (log log 𝑛) 2 ) Amortized Expected Time. Theoretics 2 (2023), 6:1–6:56. https://doi.org/10.46298/theoretics.23.6 [37] Bruce M. Kapron, Valerie King, and Ben Mountjoy. 2013. Dynamic graph connectivity in polylogarithmic worst case time. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 1131–1142. [38] Richard M. Karp, Scott Shenker, and Christos H. Papadimitriou. 2003. A Simple Algorithm for Finding Frequent Elements in Streams and Its Application to Load Balancing. In Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). 1–10. https://doi.org/10.1145/777412.777415 [39] Maksim Kitsak, Lazaros K. Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H. Eugene Stanley, and Hernán A. Makse. 2010. Identification of Influential Spreaders in Complex Networks. Nature Physics 6, 11 (2010), 888–893.

https://doi.org/10.1038/nphys1746 [40] Haewoon Kwak, Changhyun Lee, Hosung Park, and Sue Moon. 2010. What is Twitter, a Social Network or a News Media?. In Proceedings of the 19th International Conference on World Wide Web (WWW). [41] Julian J McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks.. In NIPS, Vol. 2012. Citeseer, 548–56. [42] Andrew McGregor. 2014. Graph stream algorithms: a survey. ACM SIGMOD Record 43, 1 (2014), 9–20. [43] Alan Mislove, Massimiliano Marcon, Krishna P. Gummadi, Peter Druschel, and Bobby Bhattacharjee. 2007. Measurement and Analysis of Online Social Networks. In Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC). 29–42. https://doi.org/10.1145/1298306.1298311 [44] Jayadev Misra and David Gries. 1982. Finding Repeated Elements. Science of Computer Programming 2, 2 (1982), 143–152. https://doi.org/10.1016/01676423(82)90012-0 [45] S. Muthukrishnan. 2005. Data Streams: Algorithms and Applications. Foundations and Trends® in Theoretical Computer Science 1, 2 (2005), 117–236. https://doi.org/10.1561/0400000002 [46] Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. 2017. Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time. In IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 950–961. https://doi.org/10.1109/FOCS.2017.92 [47] M. E. J. Newman. 2003. The Structure and Function of Complex Networks. SIAM Rev. 45, 2 (2003), 167–256. https://doi.org/10.1137/S003614450342480 [48] OpenStreetMap contributors. 2017. Planet dump retrieved from https://planet.osm.org . https://www.openstreetmap.org. [49] Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https://networkrepository.com [50] Stephen B. Seidman. 1983. Network Structure and Minimum Degree. Social Networks 5, 3 (1983), 269–287. https://doi.org/10.1016/0378-8733(83)90028-X [51] Moshe Shaked and J. George Shanthikumar (Eds.). 2007. Stochastic Orders. Springer, New York, NY. https://doi.org/10.1007/978-0-387-34675-5 [52] Harsha Vardhan Simhadri, George Williams, Madlib-Abhimanyu, et al. 2021. Results of the NeurIPS’21 Challenge on Billion-Scale Approximate Nearest Neighbor Search. In NeurIPS 2021 Competitions and Demonstrations Track. PMLR. [53] Daniel D Sleator and Robert Endre Tarjan. 1983. A data structure for dynamic trees. J. Comput. System Sci. 26, 3 (1983). [54] Daniel D. Sleator and Robert E. Tarjan. 1985. Self-Adjusting Binary Search Trees. J. ACM 32, 3 (1985), 652–686. https://doi.org/10.1145/3828.3835 [55] David Tench, Evan West, Victor Zhang, Michael A. Bender, Abiyaz Chowdhury, J. Ahmed Dellas, Martin Farach-Colton, Tyler Seip, and Kenny Zhang. 2022. GraphZeppelin: Storage-Friendly Sketching for Connected Components on Dynamic Graph Streams. In Proceedings of the 2022 International Conference on Management of Data (Philadelphia, PA, USA) (SIGMOD ’22). Association for Computing Machinery, New York, NY, USA, 325–339. https://doi.org/10.1145/3514221.3526146 [56] David Tench, Evan T. West, Kenny Zhang, Michael Bender, Daniel DeLayo, Martin Farach-Colton, Gilvir Gill, Tyler Seip, and Victor Zhang. 2024. Exploring the Landscape of Distributed Graph Sketching. arXiv:2410.07518 [cs.DC] https://arxiv.org/abs/2410.07518 [57] Mikkel Thorup. 2000. Near-Optimal Fully-Dynamic Graph Connectivity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing (STOC). 343–350. https://doi.org/10.1145/335305.335345 [58] David P. Woodruff. 2014. Sketching as a Tool for Numerical Linear Algebra. Foundations and Trends® in Theoretical Computer Science 10, 1-2 (2014), 1–157. https://doi.org/10.1561/0400000060 arXiv:1411.4357 [cs] [59] Christian Wulff-Nilsen. 2013. Faster deterministic fully-dynamic graph connectivity. In Proceedings of the twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 1757–1769. [60] Lantian Xu, Dong Wen, Lu Qin, Ronghua Li, Ying Zhang, and Xuemin Lin. 2024. Constant-time Connectivity Querying in Dynamic Graphs. Proc. ACM Manag. Data 2, 6, Article 230 (Dec. 2024), 23 pages. https://doi.org/10.1145/3698805 [61] Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities based on Ground-truth. In IEEE International Conference on Data Mining (ICDM). [62] Shangdi Yu, Yan Gu, and Julian Shun. 2023. ParlayANN: Scalable and Deterministic Algorithms for Approximate Nearest Neighbor Search. In Proceedings of the 28th ACM SIGPLAN Annual Symposium on Principles and Practice of Parallel Programming (PPoPP).

A BalloonSketch Analysis A.1 Probability Preliminaries A.1.1

" E

Stochastic Dominance.

# ∑︁

1{𝑧 ∈ 𝐵𝑖 } =

𝑧 ∈𝑍

Definition A.1 (Stochastic Dominance). Let 𝑋 and 𝑌 be random variables over R. We use 𝑌 ⪰ 𝑋 to denote that 𝑌 stochastically dominates 𝑋 , meaning:

∑︁

E [1{𝑧 ∈ 𝐵𝑖 }]

(linearity of expectation)

𝑧 ∈𝑍

=

∑︁

Pr[𝑧 ∈ 𝐵𝑖 ]

𝑧 ∈𝑍

≤

∑︁ 1 2𝑖 𝑧 ∈𝑍

=

𝑚 2𝑖

Pr [𝑌 ≥ 𝑡] ≥ Pr [𝑋 ≥ 𝑡] , for all 𝑡 in R. This definition is equivalent to the statement that 𝐹𝑋 (𝑡) ≥ 𝐹𝑌 (𝑡) for all 𝑡 in R (note the flipped direction), where 𝐹𝑋 (𝑡) and 𝐹𝑌 (𝑡) are the cumulative distribution functions of 𝑋 and 𝑌 , respectively. Stochastically ordered variables have a number of useful closure properties, namely that they are closed under summation of independent variables: Lemma A.1. Let 𝑋 1, 𝑋 2, . . . 𝑋𝑛 be a set of independent random variables, and let 𝑌1, 𝑌2, . . . , 𝑌𝑛 be another set of independent random variables such that 𝑋𝑖 ⪯ 𝑌𝑖 for all 𝑖 ∈ ⟨𝑛⟩. Then: 𝑛 ∑︁ 𝑖=1

𝑋𝑖 ⪯

𝑛 ∑︁

𝑌𝑖 .

𝑖=1

(Adapted from Theorem 1.A.3. in Shaked & Shanthikumar [51]) A.1.2 Concentration Bounds. We will make use of the following tail bound for geometric random variables: Lemma A.2. Let {𝑌1, . . . , 𝑌𝑛 } be the sum of 𝑛 independent geometric random variables with success probability 𝑝, and 𝑘 be some fixed conÍ stant. Define 𝑌 := 𝑛𝑖=1 𝑌𝑖 . Then 𝑌 is a negative binomially distributed random variable such that: Pr [𝑌 ≥ 𝑘E[𝑌 ]] ≤ 𝑒

−𝑘𝑛 (1−1/𝑘 ) 2 2

A simple proof of this lemma can be found in [12].

A.2

Bounding the Residual Depth of BalloonSketch

Regardless of the level of independence of the hash function ℎ, the residual depth of a geometric sampling sketch column Cℎ is itself bounded by a geometric random variable. This follows from union bounding the probability that a bucket 𝑏𝑖 , or any entry below it, is non-empty, and then applying Markov’s inequality to bound the probability that any bucket of depth 𝑖 or greater is non-empty. The formal statement and proof are given below in Lemma A.3. Lemma A.3. Let 𝑀 be the random variable corresponding to the residual depth of a sketch column Cℎ (𝑥) with input 𝑥 ∈ F𝑛 . Then 𝑀 is stochastically dominated by a geometric random variable 𝑌 with 𝑝 = 1/2 and support {1, 2, . . . }. Proof. Let 𝑍 := supp(𝑥), and 𝑚 := ||𝑥 || 0 = |𝑍 |. We note that for all 𝑧 ∈ 𝑍 , it holds, by the definition of a geometric sketch column, that 1 Pr [𝑧 ∈ (𝑍 ∩ 𝐵𝑖 )] = Pr [𝑧 ∈ 𝐵𝑖 ] ≤ 𝑖 2 Thus, the expected number of non-zeros in 𝑏𝑖 is:

We bound the probability that 𝑏𝑖 is non-empty, by Markov’s inequality: !

" ∑︁

Pr [|𝐵𝑖 | > 0] = Pr

#

1{𝑧 ∈ 𝐵𝑖 } ≥ 1

𝑧 ∈𝑍

" ≤E

# ∑︁

1{𝑧 ∈ 𝐵𝑖 }

𝑧 ∈𝑍

𝑚 2𝑖 Let 𝑤 := ⌈log2 𝑚⌉. Then for all 𝑖 ≥ 0: ≤

𝑚 2𝑤+𝑖 1 2log2 𝑚 ≤ ⌈log 𝑚⌉ · 𝑖 2 2 2 1 ≤ 𝑖 2

Pr[|𝐵 𝑤+𝑖 | > 0] ≤

Let (𝐺 1, 𝐺 2, . . . ) be the sequence of random variables such that 𝐺𝑘 is equal to 1 if there exists a non-empty bucket with depth greater than or equal to𝑤 +𝑘, and 0 otherwise. Each𝐺𝑘 is a Bernoulli random variable with 𝑝 = 2/2𝑤+𝑘 , and is 1 if and only if a non-empty bucket exists at or below 𝑏 𝑤+𝑘 : Ü  ∞ ∞
 1 ∑︁ 1 Pr [𝐺𝑘 = 1] := Pr  𝐵 𝑤+𝑗+1 > 0  ≤ 𝑘 𝑗  𝑗=𝑘  2 𝑗=0 2   2 ≤ 𝑘 2 Pr[𝐺 0 = 1] ≤ 1

Let 𝑋 be a random variable equal to the smallest non-negative integer 𝑗 such that 𝑏 𝑤+𝑗 and every bucket in Cℎ below |𝑏 𝑤+𝑗 | are empty. 𝑋 := min{ 𝑗 ∈ Z+ | 𝐺 𝑗 = 0} This definition implies that 𝑤 + 𝑗 is the depth of Cℎ , and thus such a 𝑗 would be the residual depth of Cℎ , unless the residual depth is equal to 0, in which case 𝑗 is one more than the residual depth. Accordingly, 𝑋 is at most the residual depth of Cℎ , plus one. We can thus say that, if 𝑀 is the R.V. for the residual depth, 𝑀 ≤ 𝑋 statewise (this is a stronger condition than 𝑀 ⪯ 𝑋 , as it implies that Pr[𝑋 ≥ 𝑘 | 𝑀 ≥ 𝑘] = 1). Since 𝐺𝑏 = 1 =⇒ 𝐺𝑎 = 1 and 𝐺𝑎 = 0 =⇒ 𝐺𝑏 = 0 for all 𝑎 ≤ 𝑏:

𝑀 ≥ 𝑘 =⇒ 𝑋 ≥ 𝑘 ⇐⇒

𝑘 Û

not matter. It could be identical for all columns, as is the case during streaming ingestion for the AGM sketch and it’s variants.

! 𝐺𝑗 = 1

⇐⇒ 𝐺𝑘 = 1

𝑗=0

thus: Pr[𝑀 ≥ 𝑘] ≤ Pr[𝑋 ≥ 𝑘] = Pr[𝐺𝑘 = 1] ≤

2 2𝑘

Pr[𝑀 ≥ 0] = 1

Lemma A.5. Given a set of sketch columns {Cℎ1 , . . . , Cℎ𝐿 }, the expected sum of residual depths is Θ(𝐿). Proof. Let 𝑀𝑖 be the random variable for the residual depth of Cℎ𝑖 . By linearity of expectation, " 𝐿 # 𝐿 ∑︁ ∑︁ E 𝑀𝑖 = E[𝑀𝑖 ] 𝑖=1

𝑖=1

≤ Let 𝑌 be a geometric random variable with 𝑝 = 1/2 and support Z+ . Then: Pr[𝑌 ≥ 𝑘] =

∞ ∑︁ 1

2𝑗 𝑗=𝑘 ∞

=

1 ∑︁ 1 2𝑘 𝑗=0 2 𝑗

2 2𝑘 ≥ Pr[𝑀 ≥ 𝑘]

=

for 𝑘 ∈ Z+ . We deal with the case that of 𝑘 = 0 separetely (noting

𝐿 ∑︁

2 ≤ 2𝐿

(Lemma A.3)

𝑖=1

□ Theorem A.6. Given a set of sketch columns {Cℎ1 , . . . , Cℎ𝐿 } with independent randomness, the sums of residual depths across all Cℎ𝑖 is at most Θ(𝐿 + log(𝑛)) with probability at least 1 − 1/𝑛𝑐 . Proof. Let 𝑀𝑖 be the random variable for the residual depth of Í𝐿 𝑀𝑖 , the sum of residual depths across all columns. Cℎ𝑖 . Let 𝑀 be 𝑖=1 Let {𝑌1, . . . , 𝑌𝐿 } be a set of independent geometric random vaiables Í𝐿 with 𝑝 = 1/2 and support Z+ . Let 𝑌 := 𝑖=1 𝑌𝑖 . By Lemma A.2, 𝑌 is a negative binomially distributed random variable such that: Pr [𝑌 ≥ 𝑘E[𝑌 ]] ≤ 𝑒

−𝑘𝐿 (1−1/𝑘 ) 2 2

that, given how 𝑌 is defined, 0 is not typically in it’s support): Pr[𝑌 ≥ 0] ≥ Pr[𝑌 ≥ 1] = 1 ≥ Pr[𝑀 ≥ 0]

Assume 𝐿 ≥ 𝑏 ln 𝑛 for some constant 𝑏 ∈ R+ . Choosing 𝑘 = 4𝑏𝑐, for 𝑐 ≥ 1, and noting (by linearity of expectation) that E[𝑌 ] = 2𝐿: 9

Therefore, it holds for all 𝑡 ∈ N that Pr[𝑌 ≥ 𝑡] ≥ Pr[𝑀 ≥ 𝑡] (thus, 𝑌 ⪰ 𝑀). □ Corollary A.4 (Expected Residual Depth). Given a geometric sampling sketch column Cℎ with input 𝑎 ∈ R𝑛 , the expected residual depth is Θ(1). Proof. Let 𝑌 be a geometric random variable with 𝑝 = 1/2 and support Z+ . Since 𝑌 ⪰ 𝑀 by Lemma A.3, it follows that E[𝑀] ≤ E[𝑌 ] ≤ 2. □

A.3

Aggregating Residual Depths Across Multiple Sketch Columns

Often, sketching algorithms use multiple sketch columns with independent randomness. The connectivity algorithms of AGM [3] (and it’s derivatives such as GraphZeppelin [55]), for example, require Θ(log 𝑛) sketches with constant success probability. This independent randomness, combined with the properties of sums of independent geometrically distributed random variables, allows one to bound the sums of the residual depths for geometric sampling sketch columns both in expectation and with high probability, which in turn is also an upper bound on the total number of deep buckets. Notably, as long as the hash functions ℎ drawn for each Cℎ have independent randomness, the value of the sketched vector 𝑎 does

Pr[𝑌 ≥ 8𝑏𝑐𝐿] ≤ 𝑒 −2𝑏𝑐𝐿· 16  𝑐 ≤ 𝑒 𝑏𝐿 1 𝑛𝑐 Therefore, the probability that 𝑌 exceeds 8𝑏𝑐𝐿 is at most 1/𝑛𝑐 . Í Í By Lemma A.3, 𝑀𝑖 ⪯ 𝑌𝑖 for all 𝑖. Since 𝑀 = 𝑀𝑖 and 𝑌 = 𝑌𝑖 , it follows from Lemma A.1 that 𝑀 ⪯ 𝑌 . Therefore, ≤

Pr[𝑀 ≥ 8𝑏𝑐𝐿] ≤ Pr[𝑌 ≥ 8𝑏𝑐𝐿]

(𝑀 ⪯ 𝑌 )

≤ 1/𝑛𝑐 Note that in the case that 𝐿 < 𝑏 ln(𝑛), we can simply suppose we add an additional 𝑏 ln(𝑛) geometric random variables to 𝑌 , and call this new variable 𝑌ˆ . From the tail bounds above it follows that 𝑌ˆ is Θ(𝐿 + 𝑏 ln(𝑛)) with high probability, and since 𝑌 ≤ 𝑌ˆ statewise, we conclude that𝑌 is Θ(𝐿+𝑏 ln(𝑛)) with at least that probability. The application to 𝑀 via stochastic dominance follows exactly as above. □ Theorem 1.3 (BalloonSketch). There exists an ℓ0 -sampler, BalloonSketch, such that given 𝐿 independent BalloonSketches, each sketching the same vector 𝑥 ∈ F𝑛 with 𝑚 = ∥𝑥 ∥ 0 : (1) The total space usage of the sketches is 𝑂 (𝐿 log 𝑚 + log 𝑛) w.h.p. (2) The total cost of one update to each sketch is 𝑂 (𝐿 + log 𝑛) w.h.p.

A.4

BalloonSketch Space and Time Complexity

Proof. The total space for number of initialized non-deterministic buckets for a BalloonSketch is equal to ⌈log2 𝑚⌉ plus the residual depth. Theorem A.6 bounds the total residual depth as Θ(𝐿 + log(𝑛)) w.h.p.. The update cost for a single coordinate 𝑥 is upper bounded by the sums of the depths derived from ℎ𝑖 (𝑥) for the 𝑖-th BalloonSketch; if the depth of the coordinate happens to be greater or equal to that of depth of the sketch, we may have to reallocate the BalloonSketch to shrink. Let 𝑌𝑖 be the depth of a single update 𝑥 in column 𝑖, this is stochastically dominated by some geometric random variable 𝐺𝑖 by Í𝐿 𝑌𝑖 = O (𝐿 + log 𝑛) w.h.p. by an identical construction, and thus 𝑖=1 argument to the one found in Theorem A.6. Therefore, the update cost is O (𝐿 + log 𝑛) w.h.p. The correctness and sampling probability follow from the proof for CameoSketch found in [56]. □

B

Hybrid Streaming Connectivity Proofs

Lemma B.1. The total space usage of the hybrid streaming algorithm is 𝑂 (𝑉 + 𝐸) and 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. Proof. First we prove the 𝑂 (𝑉 + 𝐸) w.h.p. space bound. We start by arguing that for each vertex𝑣 with degree𝑑 𝑣 , it uses𝑂 (1+𝑑 𝑣 ) space w.h.p. If 𝑣 is in explicit form it requires Θ(1+𝑑 𝑣 ) space. If 𝑣’s adjacency list is stored as a BalloonSketch matrix, then 𝑑 𝑣 > 𝛿/2, meaning 𝑑 𝑣 = Ω(log 𝑉 log log 𝑉 )). Per Theorem 1.3, and using 𝐿 = Θ(log 𝑉 ), the space usage is 𝑂 (𝐿 log 𝑑 𝑣 + log 𝑉 ) = 𝑂 (log 𝑉 log 𝑑 𝑣 ) w.h.p. Since 𝑑 𝑣 is at most 𝑉 , the space used by a BalloonSketch matrix for 𝑣 is also 𝑂 (1 + 𝑑 𝑣 ) w.h.p. Summing over all vertices, the total space usage is: ! ∑︁ ∑︁ 𝑂 (1 + 𝑑 𝑣 ) = 𝑂 (𝑉 ) + 𝑂 𝑑 𝑣 = 𝑂 (𝑉 + 𝐸) w.h.p. 𝑣∈V

𝑣∈V

Next we prove the 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. space bound. In this case, we will argue that each vertex 𝑣 with degree 𝑑 𝑣 uses 𝑂 (log 𝑉 log(2 + 𝑑 𝑣 )) space w.h.p. For a vertex in explicit form, we have 𝑑 𝑣 ≤ 𝛿 = Θ(log 𝑉 log log 𝑉 ). At the threshold (𝑑 𝑣 = 𝛿), the set’s space usage (BBST) is Θ(log 𝑉 log log 𝑉 ), which matches the desired bound of 𝑂 (log 𝑉 log(2 +𝑑 𝑣 )) = 𝑂 (log 𝑉 log(2 + log 𝑉 log log 𝑉 )) = 𝑂 (log 𝑉 log log 𝑉 ). For all degrees below the threshold (𝑑 𝑣 < 𝛿), the bound 𝑂 (log 𝑉 log(2 + 𝑑 𝑣 )) remains valid because the ratio, 𝑅(𝑑) = 𝑑/log(2 + 𝑑), is monotonically increasing for 𝑑 ≥ 1. For a vertex in sketch form, we have 𝑑 𝑣 = Ω(log 𝑉 log log 𝑉 ). Per Theorem 1.3, the space of the BalloonSketch matrix with 𝐿 = Θ(log 𝑉 ) is 𝑂 (log 𝑉 log(2 + 𝑑 𝑣 )) w.h.p. (since the number of nonzero elements in the sketched vector is 𝑚 = 𝑑 𝑣 ). By a union bound over all 𝑉 vertices, the total space usage is: ∑︁ ∑︁ log 𝑉 log(2 + 𝑑 𝑣 ) = 𝑂 (𝑉 ) + 𝑂 (log 𝑉 ) log(2 + 𝑑 𝑣 ) w.h.p. 𝑣∈V

𝑣∈V

Since log(2 + 𝑥) is concave, applying Jensen’s inequality: !   1 ∑︁ 1 ∑︁ 2𝐸 log(2 + 𝑑 𝑣 ) ≤ log 2 + 𝑑 𝑣 = log 2 + . 𝑉 𝑣 ∈𝑉 𝑉 𝑣 ∈𝑉 𝑉 Substituting this back into the total space expression:      2𝐸 𝐸 𝑂 (𝑉 )+𝑉 ·𝑂 (log 𝑉 )·log 2 + = 𝑂 𝑉 log 𝑉 log 2 + w.h.p. 𝑉 𝑉

Finally, we note that the IBLT for a vertex 𝑣 in sketch form uses Θ(log 𝑉 log log 𝑉 ) space which is always dominated by the sketch space since 𝑑 𝑣 = Ω(log 𝑉 log log 𝑉 ), so the space used by the sketch is Ω(log 𝑉 log log(2 + log 𝑉 log log 𝑉 )) = Ω(log 𝑉 log log 𝑉 ) w.h.p. □ Lemma B.2. The hybrid streaming algorithm processes each edge insertion and deletion in 𝑂 (log 𝑉 ) amortized time with high probability. Proof. First, we bound the base cost of an update that does not trigger a vertex transition. As established, explicit sets are implemented as BBSTs, so insertion, deletion, and search times are all loosely upper bounded by 𝑂 (log 𝑉 ). If the edge connects two sketchform vertices, inserting or deleting the edge requires updating the BalloonSketch matrix and IBLT of both endpoints, which takes 𝑂 (log 𝑉 ) time w.h.p. Thus, the base cost of any single stream update is bounded by 𝑂 (log 𝑉 ) w.h.p. Next, we bound the computational cost of vertex promotions and demotions. A vertex 𝑢 is promoted from explicit form to sketch form when its degree reaches 𝛿. Vertex 𝑢 initializes a new sketch and IBLT, and redistributes its 𝛿 explicitly stored edges. For each edge, 𝑢 either adds it to its new sketch and issues an update to a sketch-form neighbor (costing 𝑂 (log 𝑉 ) w.h.p.), or pushes it to an explicit-form neighbor’s set (costing 𝑂 (log 𝑉 )). Summing over all 𝛿 edges, the total cost of a promotion is 𝑂 (𝛿 log 𝑉 ) w.h.p. Similarly, a vertex 𝑢 demotes from sketch form to explicit form when its degree drops to 𝛿/2. Vertex 𝑢 decodes its IBLT to recover at most 𝛿/2 edges (taking 𝑂 (𝛿) time), builds a new explicit set (taking 𝑂 (𝛿 log 𝑉 ) time), and issues deletions to its sketch-form neighbors (taking 𝑂 (𝛿 log 𝑉 ) time w.h.p.). The total cost of a demotion operation is 𝑂 (𝛿 log 𝑉 ) w.h.p. Once a vertex is promoted or demoted, it must experience an absolute net change of at least 𝛿/2 edge insertions or deletions before it can transition again. We can therefore distribute the 𝑂 (𝛿 log 𝑉 ) transition cost evenly across these Ω(𝛿) required stream updates, yielding an amortized cost of 𝑂 (log 𝑉 ) per update. □ Connected Components Queries. Our connected component query algorithm uses ideas from that of Ahn et al. (described in Section 2.2). However, their algorithm does not work directly because we have some vertices store their adjacency list in explicit form. Recall that the ℓ0 sketching math requires every internal edge to be stored symmetrically by both endpoints so they cancel out via XOR summation. If an edge were stored explicitly by an array on one side and sketched on the other, it would fail to cancel, resulting in the query failing. Our asymmetric update rule was designed specifically to prevent this: by keeping mixed edges out of the sketches entirely and only sketching edges when both endpoints are in sketch form, we preserve the required mathematical parity. This allows us to safely execute the query using a multi-phase algorithm. First, we run a standard spanning forest algorithm (e.g. BFS) over all edges stored in explicit form across the entire graph. This effectively collapses the graph into a set of disjoint super-components, such that any edges between them are stored as sketch-to-sketch edges in our hybrid algorithm. For each resulting super-component 𝐶, we generate its aggregate BalloonSketch matrix by computing

the bitwise XOR sum of the sketches of all sketch-form vertices 𝑣 ∈ 𝐶. Vertices in explicit-form contribute nothing to this sum. We treat the aggregated super-components as individual super-vertices and execute the standard Borůvka-style query algorithm of Ahn et al. on their aggregated BalloonSketch structures to find the remaining cross-component edges and finalize the spanning forest. We prove in Appendix B that queries are correct w.h.p. and take 𝑂 (𝑉 log2 𝑉 ) time. Lemma B.3. The hybrid streaming connected components query algorithm runs in 𝑂 (𝑉 log2 𝑉 ) time and is correct w.h.p. Proof. We bound the time complexity by analyzing the multiphase execution. The first phase runs a standard spanning forest algorithm (e.g., BFS) over the explicitly stored edges, which takes 𝑂 (𝑉 + 𝐸 exp ) time. Because vertices only store explicit edges up to the density threshold 𝛿 = Θ(log 𝑉 log log 𝑉 ), the total number of explicit edges is 𝐸 exp ≤ 𝑉 𝛿. This BFS phase therefore strictly takes 𝑂 (𝑉 log 𝑉 log log 𝑉 ) time. In the second phase, aggregating the sketches and executing the standard AGM-style Borůvka query takes at most 𝑂 (𝑉 log2 𝑉 ) time. This second phase dominates the runtime, giving an overall time complexity of 𝑂 (𝑉 log2 𝑉 ). For correctness, the first phase is deterministically correct: the BFS evaluates explicitly stored edges and perfectly groups the graph into super-components. The algorithm then relies on the standard AGM framework to resolve the remaining sketch-to-sketch edges. Because the ℓ0 samplers guarantee the discovery of cross-component edges with high probability, the overall algorithm correctly outputs the final spanning forest with high probability. □

C

𝑇∑︁ −1 O (log(𝑉 ℓ,𝑡  ∑︁ ) ) 𝑁 ∑︁ 𝑡 =0

𝐷 (ℓ, 𝑡) :=

of the sketch seed) that is stochastically dominated by a geometric random variable. The sum of depths for all internal UFO tree nodes across all 𝑇 tiers is bounded by:

Í𝑁ℓ,𝑡 ℓ,𝑡 !   𝑖=1 𝑑𝑖 lg 𝑑𝑖ℓ,𝑡 ≤ 𝑁 ℓ,𝑡 lg 𝑁 ℓ,𝑡 𝑖=1   2𝐸 ℓ ≤ 𝑁 ℓ,𝑡 lg 𝑁 ℓ,𝑡 !  ℓ 2𝐸 5 𝑉 lg ≤𝛼
ℓ 6 𝛼 56 𝑉  ℓ      5 6 2𝐸 ≤𝛼 1 − lg(𝛼) + ℓ lg 𝑉 lg 6 5 𝑉

𝑁 ℓ,𝑡 ∑︁

Where 𝛼 ∈ (0, 1) is an unknown real number such that 𝑁 ℓ,𝑡 = 𝛼 (5/6) ℓ 𝑉 . Upper bounding the r.h.s. with respect to 𝛼 gives  ℓ      5 6 2𝐸 1 − lg(𝛼) + ℓ lg 𝑉 lg 6 5 𝑉  ℓ      5 6 2𝐸 ≤ · 𝛼 (1 − lg(𝛼)) + 𝛼ℓ lg 𝑉 lg 6 5 𝑉      ℓ  2𝐸 5 6 · 1.07 + ℓ lg 𝑉 lg ≤ 6 5 𝑉

𝐷 (ℓ, 𝑡) ≤ 𝛼

Lemma 4.1. There exists a dynamic connectivity algorithm with space complexity 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. The update complexity is 𝑂 (log4 𝑉 ). The query complexity is 𝑂 (log 𝑉 /log log 𝑉 ).

lg(𝑑𝑖ℓ,𝑡 ) + 𝑌𝑖ℓ,𝑡 ℓ,𝑡 where 𝑌𝑖 is a random variable (determined by the randomness

𝑖=1

First, we show that the contribution from the lg(𝑑𝑖ℓ,𝑡 ) terms is O (𝑉 log 𝑉 log(𝐸/𝑉 )). For a fixed tier 𝑡 and fixed level ℓ, we know that 𝑁 ℓ,𝑡 ≤ (5/6) ℓ 𝑉 . Let 𝐸 ℓ ≤ 𝐸 be the number of external edges among our level ℓ partition, i.e., the edges that exist between two different nodes at level ℓ but not the edges internal to a node. Applying Jensen’s inequality:

BalloonSketch Dynamic Connectivity Analysis

Proof. We prove the space bound. Our data structure consists of 𝑇 = Θ(log(𝑉 )) tiers, matching the number needed in CUPCaKE, each with a UFO tree U 𝑡 maintaining aggregates for a subtree query (where the aggregate is a single BalloonSketch). For each UFO tree U 𝑡 , there are levels U 0,𝑡 , U 1,𝑡 , . . . , U ℓ,𝑡 , . . . , U O (log(𝑉 ) ),𝑡 . Level ℓ of a UFO tree has at most 5/6 as many nodes as level ℓ −1. Each level ℓ consists of 𝑁 ℓ,𝑡 ≤ (5/6) ℓ 𝑉 nodes, each of which with an aggregate BalloonSketch. Each node represents a subset of the vertices, and the nodes at each level ℓ collectively form a partitioning of the vertices. Let 𝑈𝑖ℓ,𝑡 be the 𝑖th node at level ℓ of the tier 𝑡 UFO tree for 1 ≤ 𝑖 ≤ 𝑁 ℓ,𝑡 (assigning an arbitrary ordering to the nodes at each level). Let 𝑑𝑖ℓ,𝑡 be the number of edges in the cut corresponding to (V, V \𝑈𝑖ℓ,𝑡 ). Intuitively 𝑑𝑖ℓ,𝑡 is the “degree” (number of edges coming out) of the 𝑖-th cluster at level ℓ in the UFO tree for tier 𝑡. The depth of the BalloonSketch for 𝑈𝑖ℓ,𝑡 is:

ℓ=0

   lg 𝑑𝑖ℓ,𝑡 + 𝑌𝑖ℓ,𝑡

The upper bounding of 𝛼 (1 − lg(𝛼)) was found analytically (the maximum is achieved at 𝛼 = 2/𝑒). Across all levels ℓ of a fixed tier 𝑡, the sum of depths of stored sketch aggregates is: O (log ∑︁𝑉 ) ℓ=0

O (log ∑︁𝑉 ) 

ℓ      6 2𝐸 5 𝐷 (ℓ, 𝑡) ≤ · 1.07 + ℓ lg 𝑉 lg 6 5 𝑉 ℓ=0   O (log      ∑︁𝑉 ) 5 ℓ 2𝐸 6 ≤ 𝑉 lg · · 1.07 + ℓ lg 𝑉 6 5 ℓ=0        ℓ ! ∞ ∞ ∑︁ 5 ℓ 2𝐸 6 ∑︁ 5 ≤ 𝑉 lg · 1.07 + lg ℓ 𝑉 6 5 ℓ=0 6 ℓ=0       2𝐸 6 · 1.07 · 6 + lg · 30 ≤ 𝑉 log 𝑉 5   2𝐸 ≤ 15𝑉 log 𝑉

Summing across all 𝑇 tiers:

𝑇∑︁ −1 O (log(𝑉 ℓ,𝑡 ∑︁ ) ) 𝑁 ∑︁ 𝑡 =0

ℓ=0

−1 O (log(𝑉   𝑇∑︁ ∑︁ ) ) lg 𝑑𝑖ℓ,𝑡 = 𝐷 (ℓ, 𝑡) 𝑡 =0

𝑖=1

𝑇∑︁ −1

ℓ=0



 2𝐸 𝑉 𝑡 =0    2𝐸 = O 𝑉 log 𝑉 log 𝑉 Meanwhile, the sums of residual depths across all sketches is: ≤

𝑇∑︁ −1 O (log(𝑉 ℓ,𝑡 ∑︁ ) ) 𝑁 ∑︁ 𝑡 =0

ℓ=0

15𝑉 log

D

Hybrid Dynamic Connectivity Proofs

Lemma D.1. The space complexity of our hybrid dynamic connectivity algorithm is 𝑂 (𝑉 + 𝐸) w.h.p. 𝑌𝑖ℓ,𝑡

𝑖=1

Let 𝐿 be the maximum level across all 𝑇 tiers and note that 𝐿 = O (log(𝑉 )). Let ( 𝑌 ℓ,𝑡 ℓ,𝑡 ˆ 𝑌𝑖 = 𝑖 0

equivalent to other dynamic tree data structures, and we do not modify the overall update and query algorithms of Gibb’s algorithm. For the sake of clean arithmetic we assumed WLOG that each vertex (and each cluster) has a degree of at least 2; if a vertex has degree zero, it still uses Θ(1) words of space per each Θ(log 𝑉 ) tier, and thus the space is always at least Ω(𝑉 log 𝑉 ). Our final space usage thus has a plus two added to the second logarithm to account for this, yielding O (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )). □

if UFO node 𝑈𝑖ℓ,𝑡 exists otherwise

Proof. First we prove the space is 𝑂 (𝑉 + 𝐸) w.h.p. Let 𝑉𝐷 and 𝐸𝐷 be the number of vertices and edges in 𝐴𝐿𝐺 𝐷 respectively. Let 𝑀𝐸𝑀𝐷 be the random variable for the space usage of 𝐴𝐿𝐺 𝐷 , and 𝑀𝐸𝑀𝑆 be the space usage of 𝐴𝐿𝐺𝑆 . Due to Lemma 4.1, we know that 𝑀𝐸𝑀𝐷 = 𝑂 (𝑉𝐷 log 𝑉 log(2 + 𝐸𝐷 /𝑉𝐷 )) with high probability in𝑉 . If 𝐸𝐷 ≥ 𝑉𝐷 log 𝑉 log(2+𝐸𝐷 /𝑉𝐷 ), then this space is 𝑂 (𝐸) with high probability since 𝐸 ≥ 𝐸𝐷 . Otherwise, we have: 𝐸𝐷 ≤ 𝑉𝐷 log 𝑉 log(2 + 𝐸𝐷 /𝑉𝐷 ) ≤ 2𝑉𝐷 log2 𝑉 .

and note: 𝑇∑︁ −1 ∑︁ 𝐿 𝑁 ℓ,𝑡 ∑︁

𝑌𝑖ℓ,𝑡 =

ℓ 𝑇∑︁ −1 ∑︁ 𝐿 (5/6) ∑︁

𝑡 =0 ℓ=0 𝑖=1

𝑡 =0 ℓ=0

=

𝐿 (5/6) ∑︁ ∑︁ ℓ=0

Therefore, 𝑌ˆ𝑖ℓ,𝑡

𝑀𝐸𝑀𝐷 = 𝑂 (𝑉𝐷 log 𝑉 log(2 + 𝐸𝐷 /𝑉𝐷 ))

𝑖=1 ℓ

𝑇∑︁ −1

! 𝑌ˆ𝑖ℓ,𝑡

𝑡 =0

𝑖=1

Focusing on a fixed ℓ and 𝑖 at the sum over the tiers, define new geometric random variables 𝐺 0, . . . 𝐺𝑇 −1 . By the definition of 𝑌𝑖ℓ,𝑡 it is clear that 𝐺𝑖 ⪰ 𝑌ˆ𝑖ℓ,𝑡 . Furthermore, since the randomness of 𝑌ˆ𝑖ℓ,𝑡 is determined by the tier 𝑡 and each R.V. in the set {𝑌ˆ𝑖ℓ,𝑡 | 0 ≤ 𝑡 ≤ 𝑇 − 1} has a unique 𝑡, the set of 𝑌ˆ𝑖ℓ,𝑡 are mutually independent. Lemma A.1 then implies: 𝑇∑︁ −1

𝑌ˆ𝑖ℓ,𝑡 ⪯

𝑡 =0

𝑇∑︁ −1

𝐺𝑡

𝑡 =0

and therefore: 𝑇∑︁ −1 ∑︁ 𝐿 𝑁 ℓ,𝑡 ∑︁

𝑌𝑖ℓ,𝑡 ⪯

𝑡 =0 ℓ=0 𝑖=1

𝐿 (5/6) ∑︁ ∑︁ ℓ=0

𝑖=1

ℓ

𝑇∑︁ −1

! 𝐺𝑡

𝑡 =0

Í −1 By Lemma A.2, w.h.p., 𝑇𝑡 =0 𝐺𝑡 = O (𝑇 + log(𝑉 )) = O (log(𝑉 )) for a fixed ℓ and 𝑖. Union bounding over all O (𝑉 ) choices of (ℓ, 𝑖): 𝑇∑︁ −1 ∑︁ 𝐿 𝑁 ℓ,𝑡 ∑︁

𝑌𝑖ℓ,𝑡 = O (𝑉 log(𝑉 ))

𝑡 =0 ℓ=0 𝑖=1

with high probability, which is dominated by the O (𝑉 log 𝑉 log(𝐸/𝑉 )) minimum depth implied by the lg(𝑑𝑖ℓ,𝑡 ) terms. Therefore, the total space usage is O (𝑉 log 𝑉 log(𝐸/𝑉 )) with high probability. The update bound and the query bound follow from the fact that the costs of Link and Cut operations in UFO tree is asymptotically

= 𝑂 (𝑉𝐷 log 𝑉 log(2 + 2 log2 𝑉 )) = 𝑂 (𝑉𝐷 log 𝑉 log log 𝑉 ) with high probability. Every vertex in 𝐴𝐿𝐺 𝐷 has degree at least 𝛿/2 = log 𝑉 log log 𝑉 /2, therefore the total number of edges is 𝐸 ≥ 𝑉𝐷 log 𝑉 log log 𝑉 /4. Thus, in this case as well, the space in 𝐴𝐿𝐺 𝐷 is 𝑂 (𝐸) with high probability. 𝑀𝐸𝑀𝑆 is 𝑂 (𝑉 + 𝐸) since the graph stored by 𝐴𝐿𝐺𝑆 is a subgraph of G, and the Cluster Forest algorithm uses linear space. The space usage in our degree storage is clearly 𝑂 (𝑉 ). The space usage of the 𝑉𝐷 𝛿-sparse recovery sketches is 𝑂 (𝑉𝐷 log 𝑉 log log 𝑉 ), which again is 𝑂 (𝐸) since 𝐸 ≥ 𝑉𝐷 log 𝑉 log log 𝑉 /4. Therefore, the total space complexity 𝑀𝐸𝑀𝐷 + 𝑀𝐸𝑀𝑆 along with auxiliary structures is 𝑂 (𝑉 + 𝐸) with high probability. Finally the space usage in IBLT’s is 𝑂 (𝑉𝐷 log 𝑉 log log 𝑉 ) which is dominated by 𝑀𝐸𝑀𝐷 . The boolean and global degree for each vertex only take 𝑂 (𝑉 ) total space. □ Lemma D.2. The space complexity of our hybrid dynamic connectivity algorithm is 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) w.h.p. Proof. Let 𝑉𝐷 and 𝐸𝐷 be the number of vertices and edges in 𝐴𝐿𝐺 𝐷 respectively. Let 𝑀𝐸𝑀𝐷 be the random variable for the space usage of 𝐴𝐿𝐺 𝐷 , and 𝑀𝐸𝑀𝑆 be the space usage of 𝐴𝐿𝐺𝑆 . We know that 𝑀𝐸𝑀𝐷 = 𝑂 (𝑉𝐷 log 𝑉 log(2 + 𝐸𝐷 /𝑉𝐷 )) with high probability in 𝑉 . Note that 𝑓 (𝑥) = 𝑥 log(2 + 𝑦/𝑥) is a monotonically increasing function for positive 𝑥 and a fixed positive 𝑦. Thus, since 𝑉𝐷 ≤ 𝑉 and 𝐸𝐷 ≤ 𝐸, we have 𝑀𝐸𝑀𝐷 = 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) with high probability in 𝑉 . Because of the linear space complexity of the Cluster Forest algorithm, 𝑀𝐸𝑀𝑆 = 𝑂 (𝑉 + 𝐸𝑆 ), where 𝐸𝑆 is the number of edges in 𝐴𝐿𝐺𝑆 . The spanning forest of 𝐴𝐿𝐺 𝐷 contributes at most 𝑉 − 1 edges

to 𝐸𝑆 . The remaining edges must be sparse edges (the set of sparse edges may overcount the remaining edges in 𝐴𝐿𝐺𝑆 because some sparse edges may be in 𝐴𝐿𝐺 𝐷 since we only demote vertices with degree < 𝛿/2, but no dense edges other than the spanning forest can be in 𝐴𝐿𝐺𝑆 ). To upper bound the number of sparse edges, we can simply sum the degrees of every sparse vertex. This results in edges between two sparse vertices being counted twice, and edges between a dense and a sparse vertex being counted once. Since every sparse vertex has degree < 𝛿, the number of sparse edges is < 𝑉 𝛿, so 𝐸𝑆 < 𝑉 log 𝑉 log log 𝑉 . If 𝐸 < 𝑉 log 𝑉 log(2 + 𝐸/𝑉 ) then 𝑀𝐸𝑀𝑆 = 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) is trivially true. Else 𝐸 ≥ 𝑉 log 𝑉 log(2 + 𝐸/𝑉 ) and,   𝑉 log 𝑉 𝑉 log 𝑉 log log 𝑉 ≤ 𝑉 log 𝑉 log 2 + 𝑉   𝑉 log 𝑉 log(2 + 𝐸/𝑉 ) ≤ 𝑉 log 𝑉 log 2 + 𝑉   𝐸 ≤ 𝑉 log 𝑉 log 2 + . 𝑉 Therefore, 𝐸𝑆 = 𝑂 (𝑉 log 𝑉 log(2+𝐸/𝑉 )), and 𝑀𝐸𝑀𝑆 = 𝑂 (𝑉 +𝐸𝑆 ) = 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )). Combining both bounds, the total space complexity 𝑀𝐸𝑀𝐷 + 𝑀𝐸𝑀𝑆 is 𝑂 (𝑉 log 𝑉 log(2 + 𝐸/𝑉 )) with high probability in 𝑉 . □ Lemma D.3. The amortized update complexity of our hybrid dynamic connectivity algorithm is 𝑂 (log4 𝑉 ). Proof. An update operation (edge insertion or deletion) in our hybrid framework consists of up to three main components: (1) updating the corresponding base algorithm (𝐴𝐿𝐺 𝐷 or 𝐴𝐿𝐺𝑆 ) and auxiliary structures, (2) applying any resulting spanning forest changes from 𝐴𝐿𝐺 𝐷 to 𝐴𝐿𝐺𝑆 , and (3) handling potential vertex promotions or demotions. First, consider the cost of a standard edge update that does not trigger a promotion or demotion. If the edge is in the sparse region, we update 𝐴𝐿𝐺𝑆 . The Cluster Forest algorithm handles updates in amortized𝑂 (log2 𝑉 ) time [59]. If the edge is in the dense region, we update 𝐴𝐿𝐺 𝐷 . Our BalloonSketch-based algorithm (Section 4.1) supports updates in worst-case 𝑂 (log4 𝑉 ) time. Additionally, updating the IBLT’s for the endpoints takes 𝑂 (1) time. In the dense case, 𝐴𝐿𝐺 𝐷

may return a list of changes to its spanning forest. Sketch-based dynamic connectivity algorithms produce at most 𝑂 (log 𝑉 ) spanning forest changes per update. We must apply each of these changes to 𝐴𝐿𝐺𝑆 , which takes 𝑂 (log 𝑉 ) · 𝑂 (log2 𝑉 ) = 𝑂 (log3 𝑉 ) amortized time. Thus, the base cost of any single edge update, excluding vertex promotions/demotions, is bounded by 𝑂 (log4 𝑉 ) amortized. Next, we analyze the cost of vertex promotions and demotions. When a vertex 𝑣 is promoted (i.e., its degree reaches above 𝛿), we iterate over its 𝛿 incident edges in 𝐴𝐿𝐺𝑆 . For any edge connecting to another heavy vertex, we insert it into 𝐴𝐿𝐺 𝐷 and delete it from 𝐴𝐿𝐺𝑆 . This requires at most 𝛿 operations in 𝐴𝐿𝐺 𝐷 and 𝐴𝐿𝐺𝑆 , along with tracking the subsequent spanning forest changes. Because each standard edge move costs bounded by 𝑂 (log4 𝑉 ) amortized, the total cost of promoting a vertex is𝑂 (𝛿 log4 𝑉 ) amortized. Similarly, when a vertex 𝑣 is demoted (its degree falls down to 𝛿/2), we recover its at most 𝛿/2 incident edges from IBLT𝑣 in 𝑂 (𝛿) time, delete them from 𝐴𝐿𝐺 𝐷 , and insert them into 𝐴𝐿𝐺𝑆 . This process also involves at most 𝛿/2 edge moves, bounding the demotion cost by 𝑂 (𝛿 log4 𝑉 ) amortized. To bound the amortized cost, we use a standard potential argument. A vertex is promoted only when its degree increases above 𝛿, and demoted only when its degree decreases to 𝛿/2. Therefore, between any two consecutive threshold crossings (a promotion followed by a demotion, or vice versa), the vertex must have undergone at least 𝛿/2 individual edge insertions or deletions incident to it. We charge the 𝑂 (𝛿 log4 𝑉 ) cost of the promotion or demotion evenly across these Ω(𝛿) updates. This adds an amortized cost of 𝑂 (𝛿 log4 𝑉 /𝛿) = 𝑂 (log4 𝑉 ) to each update. Combining the base update cost and the amortized promotion and demotion cost, the overall amortized update complexity of our hybrid framework is 𝑂 (log4 𝑉 ). □ Lemma D.4. The worst-case query complexity of our hybrid dynamic connectivity algorithm is 𝑂 (log 𝑉 /log log 𝑉 ). Proof. As described in our query algorithm (Section 4.2), any connectivity query Connected(𝑢, 𝑣) in our framework is directly answered by calling 𝐴𝐿𝐺𝑆 .Connected(𝑢, 𝑣). Because we use the Cluster Forest algorithm [59] as 𝐴𝐿𝐺𝑆 , which supports worst-case 𝑂 (log 𝑉 /log log 𝑉 ) query times, the query complexity of our hybrid framework is exactly 𝑂 (log 𝑉 /log log 𝑉 ) in the worst case. □

E

Additional Experimental Results

Table 2 shows the un-normalized results of our memory usage experiments. Table 3 shows the un-normalized results of our update speed experiments. Table 4 indicates the number of cutset tiers that were actually required for HybridSCALE and CUPCaKE. The results show that the number of tiers is always lower than the number we allocated (⌈log2 𝑉 ⌉), indicating that the Monte Carlo random algorithms never induced an error in our experiments. Also HybridSCALE can require significantly fewer tiers than CUPCaKE.

Graph

Hybrid SCALE (GB)

Cluster Forest (GB)

CUP CaKE (GB)

Google+ Friendster Twitter Orkut ENWiki Youtube RoadUSA RoadGER SIFT-RS-50K SIFT-KNN-500 MSSPACE-RS-10K MSSPACE-KNN-500 kron-13 kron-15 kron-16

0.241 65.7 38.5 3.75 3.83 0.494 10.2 5.33 2.33 10.1 1.21 10 0.0651 0.299 0.643

0.284 60.7 44.5 3.54 3.62 0.479 9.93 5.2 4.79 8.86 14.4 8.54 0.439 6.98 27.9

2.83 — — 128 — 42.8 — — 34.9 36 34.7 36 0.145 0.743 1.66

Table 2: Peak memory usage (GB) in our experiments. Entries indicated as — ran out of memory (OOM).

Graph Google+ Friendster Twitter Orkut ENWiki Youtube RoadUSA RoadGER SIFT-RS-50K SIFT-KNN-500 MSSPACE-RS-10K MSSPACE-KNN-500 kron-13 kron-15 kron-16

Hybrid SCALE (sec)

Cluster Forest (sec)

CUP CaKE (sec)

38.7 42.2K 22.9K 902 638 18 263 163 1.75K 7.59K 3.88K 6.61K 66.7 1.64K 8.41K

27.5 22.2K 11.8K 642 501 20.8 274 178 1.03K 2.36K 2.47K 1.93K 28.2 961 5.87K

440 — — 16.7K — 697 — — 7.52K 14K 10.3K 13.5K 99.2 1.53K 6.98K

Table 3: Total update time in seconds in our experiments. Entries indicated as — ran out of memory (OOM).

Graph Google+ Friendster Twitter Orkut ENWiki Youtube RoadUSA RoadGER SIFT-RS-50K SIFT-KNN-500 MSSPACE-RS-10K MSSPACE-KNN-500 kron-13 kron-15 kron-16

⌈log2 𝑉 ⌉

Hybrid SCALE

CUP CaKE

17 26 26 22 23 21 25 24 20 20 20 20 13 15 16

11 14 15 11 12 9 0 0 13 14 13 15 11 12 14

14 — — 18 — 15 — — 17 18 16 18 12 14 14

Table 4: Max number of tiers used. Entries indicated as — ran out of memory (OOM). A value of 0 indicates that HybridSCALE did not sketch anything.

Related documents

• Databases with Missing Values that are Governed by Missingness Mechanisms#1043177
• Proof-of-Retention: A Framework for Auditable Cross-Organization Data Sharing#1043178
• AkasicMEM: Governed Enterprise Memory for Agents#1043179
• Spend Classification Without Leakage: An Evaluation Harness and What It Changed in a Deployed System#1043180
• A Functional Pilot for Certified Freshness-Aware Semantic--Spatial Range Retrieval#1043181