The last four BSS posts considered streams of numerical values. While there are still many more bite-sized results to cover for such streams, I thought we’d mix things up a bit and switch to graph streams for the next four posts. We’ll consider a stream of unweighted, undirected edges and try to estimate properties of the graph defined by this stream subject to the usual constraints of stream computation (sequential access to the stream and limited memory). For this post, we focus on estimating distances.
The results we’ll discuss revolve around constructing a -spanner, a sub-graph of such that for any
where is the length of the shortest path between in graph . Obviously, given such a graph we can approximate any distance up to a factor of
So how can we construct a -spanner in the data-stream model? Here’s a very simple algorithm: Intialize to and on receiving edge , add the edge to if and only if .
It’s easy to show that is indeed a -spanner because, for each edge on a shortest path in , either includes or a path between and of length at most . The space taken by the algorithm is just the space required to store . How large can this be? Well, note that has girth at least , i.e., it contains no cycles of length or shorter. It can be shown that such a graph has at most edges if is odd (see e.g., [Bollobás] or [Indyk's lecture slides]) and hence we have a stream algorithm using bits of memory that finds a approximation for any shortest path distance.
Unfortunately, the time to process each edge in the above algorithm is rather large and this spurred some nice follow-up work including [Feigenbaum et al.], [Baswana], and [Elkin]. It’s now known how to construct a -spanner in space and constant worst-case time per edge.
It’s not hard to extend these algorithms to weighted graphs (consider geometrically grouping the edge weights and constructing a spanner for each distinct edge weight) but there’s bad news for directed graphs: even determining if there exists a directed path between two nodes requires bits of memory.
BONUS! Some British English… Back in the UK, we call this
a spanner. Apparently that’s not the usual term in US English and I found this out after giving a talk at SODA back in 2005. The talk went reasonably well but, during the coffee break, numerous people asked why I’d kept on displaying pictures of wrenches throughout my talk. Whoops.
In technical writing, I normally endeavor [sic] to use US English (although I did once engage in some “colouring of paths” in a paper with a Canadian co-author). But I still think “math and stat” sounds funny :)