The Case for External Graph Sketching

Michael A. Bender, Martín Farach-Colton, Riko Jacob, Hanna Komlós, David Tench, Evan T. West · 2025

Read The Case for External Graph Sketching by Michael A. Bender, Martín Farach-Colton, Riko Jacob, Hanna Komlós, David Tench, Evan T. West (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-17563.txt.

Introduction

Michael Bender and co-authors argue for sketching huge graphs with disk storage in the loop in a 2025 paper. Streaming algorithms summarize inputs in tiny memory, but graph versions still need more fast memory than machines hold. That gap may explain why these methods see little real use.

Their external semi-streaming model keeps a graph-sized sketch mostly on disk, accessed in blocks, and prizes both small space and few disk reads. A general recipe converts any vertex-based sketch into the new model at near-best cost, backed by a matching lower bound. Converted algorithms solve connectivity, bipartiteness, spanning tree weight, min cut, and densest subgraph tasks. Several beat prior art in both streaming and external-memory models.

Catalog record

CREATORMichael A. Bender, Martín Farach-Colton, Riko Jacob, Hanna Komlós, David Tench, Evan T. West
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-17563

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

The Case for External Graph Sketching Michael A. Bender, Martín Farach-Colton, Riko Jacob, Hanna Komlós, David Tench, Evan T. West Abstract Algorithms in the data stream model use O(polylog(N)) space to compute some property of an input of size N , and many of these algorithms are implemented and used in practice. However, sketching algorithms in the graph semi-streaming model use O(Vpolylog(V)) space for a V -vertex graph, and the fact that implementations of these algorithms are not used in the academic literature or in industrial applications may be because this space requirement is too large for RAM on today’s hardware. In this paper we introduce the external semi-streaming model, which addresses the aspects of the semi-streaming model that limit its practical impact. In this model, the input is in the form of a stream and O(Vpolylog(V)) space is available, but most of that space is accessible only via block I/O operations as in the external memory model. The goal in the external semi-streaming model is to simultaneously achieve small space and low I/O cost. We present a general transformation from any vertex-based sketch algorithm to one which has a low sketching cost in the new model. We prove that this automatic transformation is tight or nearly (up to a O(\log(V)) factor) tight via an I/O lower bound for the task of sketching the input stream. Using this transformation and other techniques, we present external semi-streaming algorithms for connectivity, bipartiteness testing, (1+\varepsilon) -approximating MST weight, testing k-edge connectivity, (1+\varepsilon) -approximating the minimum cut of a graph, computing \varepsilon -cut sparsifiers, and approximating the density of the densest subgraph. These algorithms all use O(Vpoly(\log(V),\varepsilon^{-1},k) space. For many of these problems, our external semi-streaming algorithms outperform the state of the art algorithms in both the sketching and external-memory models. 1 Introduction The streaming model has been widely successful in both the theory and systems literature for a variety of reasons. In this model, the input is presented as a arbitrarily-ordered stream of updates, and the challenge is to design algorithms that compute properties of the input in small (ideally polylogarithmic) space. On the theory side, it is an elegant and simplified model that allows for the development of interesting upper bounds without getting bogged down in the details of the hardware. Despite the relative simplicity of the model, it has also been successful in the systems literature because it does capture important aspects of real computers. Specifically, it captures the idea that caches are small and fast and streams of data arrive quickly and are too big to store. The streaming model succeeded because it hit a sweet spot between the elegance needed for theoretical results and capturing the right hardware constraints for designing software. However, not all streaming problems can be solved in the streaming model. For example, most graph-theoretic problems have outputs that are by themselves too large to store in the polylogarithmically sized RAM specified by the streaming model. The graph semi-streaming model [ 28 , 53 ] was introduced in order to bridge this gap. Specifically, in the semi-streaming model we assume that we have O(V\mathrm{polylog}V) space, where V denotes the number of vertices in the input graph. The input stream is a sequence of edge insertions (and possibly deletions). The semi-streaming model has proven to be fertile soil for theoretical results for both upper and lower bounds. For example, there is a rich literature for addressing a long list of graph problems [ 5 , 3 , 54 , 28 , 53 , 36 , 32 , 6 , 21 , 10 , 46 , 37 , 44 , 24 , 47 , 4 , 57 , 22 , 42 , 12 ] , as well as computational geometric problems [ 35 , 17 , 25 , 65 , 13 , 29 ] , and hypergraph problems [ 32 , 45 , 26 , 48 , 11 , 14 , 33 ] . The semi-streaming model is elegant and captures something exciting about the structure of graph problems and their algorithms. In the general case where the stream contains deletions, all known space-efficient algorithms are linear sketches . These algorithms generate a random linear projection of the input that can be stored in O(V\mathrm{polylog}V) space. Moreover, there is strong theoretical evidence that linear sketches are universal; i.e., that any space-efficient single-pass semi-streaming algorithm with constant success probability can be formulated as a linear sketch [ 42 ] . There is a corresponding need in industry and large-scale science to process massive, dynamic graphs. A recent survey by Sahu et al . [ 58 ] of industrial uses of graph algorithms indicates that a majority of industry respondents need to process massive (at minimum multi-billion-edge) graphs, and a majority work with graphs that change over time. Scientific applications include metagenome assembly [ 31 , 56 ] , large-scale clustering [ 63 , 64 , 27 ] , and tracking social network communities that change as users add or delete friends [ 40 , 16 ] . Despite its great theoretical success and a wealth of potential applications, the semi-streaming model has not yielded a corresponding applied literature. The reason is straightforward – for practical purposes O(V\mathrm{polylog}V) space is enormously larger than RAM and will remain so for the foreseeable future. In Appendix A we illustrate this problem with a case study on the k-connectivity sketch of Ahn et al . [ 5 ] , one of the simplest and smallest graph sketch algorithms. We show that the logarithmic and constant factors in the space complexity of this algorithm are large enough that it will not save space until we have RAM sizes in the hundreds of TBs. We note in the appendix that due to a lower bound of Nelson and Yu [ 54 ] , this asymptotic space complexity cannot be significantly improved. Additionally, the k-connectivity sketch is a subroutine for many other semi-streaming algorithms such as minimum cut, spectral sparsification, and minimum spanning tree [ 5 ] . This suggests that the problem illustrated in our case study is not an isolated one but rather a general limitation of many semi-streaming algorithms. In this paper, we show that not all hope is lost. Our optimism is based on a reexamination of hardware trends. We notice that the bandwidth of high-speed storage systems is now so high that the cost of random access to RAM is comparable to the cost of sequential access to storage. On the other hand, such high-speed storage is expensive and limited in size. So one of the contributions of this paper is a modification of the semi-streaming model based on modern hardware. For a more detailed description of hardware that we use to reach these conclusions, see Appendix B . This observation about bandwidths has an interesting algorithmic implication. Many if not most advanced semi-streaming algorithms use hashing to keep sketches in RAM, and therefore the random-access bandwidth of RAM is an upper bound on their performance. 1 1 1 Sequential-access RAM is significantly faster (an order of magnitude) but existing sketch data structures do not perform updates sequentially. So a hypothetical semi-streaming algorithm that made only sequential accesses could be run

Read the complete text