We compute the singular values of an @math sparse matrix @math in a distributed setting, without communication dependence on @math , which is useful for very large @math . In particular, we give a simple nonadaptive sampling scheme where the singular values of @math are estimated within relative error with constant probability. Our proven bounds focus on the MapReduce framework, which has become the de facto tool for handling such large matrices that cannot be stored or even streamed through a single machine. On the way, we give a general method to compute @math . We preserve singular values of @math with @math relative error with shuffle size @math and reduce-key complexity @math . We further show that if only specific entries of @math are required and @math has nonnegative entries, then we can reduce the shuffle size to @math and reduce-key complexity to @math , where @math is the minimum cosine similarity for the entries being estimated. All of our bounds are independent of @math , the larger dimension. We provide open-source implementations in Spark and Scalding, along with experiments in an industrial setting.
There has been some effort to reduce the number of passes required through the matrix @math using little memory, in the streaming model . The question was posed by @cite_1 to determine in the streaming model various linear algebraic quantities. The problem was posed again by @cite_0 who asked about the time and space required for an algorithm not using too many passes. The streaming model is a good one if all the data can be streamed through a single machine, but with @math so large, it is not possible to stream @math through a single machine. Splitting the work of reading @math across many mappers is the job of the MapReduce implementation and one of its major advantages .
@cite_0 @cite_1
2950256099 1592953077 2949292204 2044334960
We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass @math -approximation streaming algorithm can be easily obtained with space @math , where @math denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space @math is granted, for every @math . Specifically, for every @math , we show that in the one-pass turnstile streaming model, in order to compute a @math -approximation, space @math is required for constant error randomized algorithms, and, up to logarithmic factors, space @math is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest. Multi-Pass Models: It is common in graph mining to consider algorithms that may take more than one pass over the stream. There has also been work in the W-Stream model in which the algorithm is allowed to write to the stream during each pass [9]. These annotations can then be utilized by the algorithm during successive passes and it can be shown that this gives sufficient power to the model for PRAM algorithms to be simulated [8]. The Stream-Sort model goes one step further and allows sorting passes in which the data stream is sorted according to a key encoded by the annotations [1]. Motivated by the trend to outsource work to commercial cloud computing services, we consider a variation of the streaming paradigm where a streaming algorithm can be assisted by a powerful helper that can provide annotations to the data stream. We extend previous work on such annotation models by considering a number of graph streaming problems. Without annotations, streaming algorithms for graph problems generally require significant memory; we show that for many standard problems, including all graph problems that can be expressed with totally unimodular integer programming formulations, only a constant number of hash values are needed for single-pass algorithms given linear-sized annotations. We also obtain a protocol achieving tradeoffs between annotation length and memory usage for matrix-vector multiplication; this result contributes to a trend of recent research on numerical linear algebra in streaming models. We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order. The main computational restriction of the model is that we have limited space and therefore cannot store all the streamed data; we are forced to make space-efficient summaries of the data as we go along. For a graph of n vertices and m edges, we show that testing many graph properties, including connectivity (ergo any reasonable decision problem about distances) and bipartiteness, requires Ω(n) bits of space. Given this, we then investigate how the power of the model increases as we relax our space restriction. Our main result is an efficient randomized algorithm that constructs a (2t + 1)-spanner in one pass. With high probability, it uses O(t .n1+1 t log2n) bits of space and processes each edge in the stream in O(t2·n1 t log n) time. We find approximations to diameter and girth via the constructed spanner. For t = Ω(log n log log n), the space requirement of the algorithm is O(n .polylog n), and the per-edge processing time is O(polylog n). We also show a corresponding lower bound of t for the approximation ratio achievable when the space restriction is O(t.n1+1 t log2n).We then consider the scenario in which we are allowed multiple passes over the input stream. Here, we investigate whether allowing these extra passes will compensate for a given space restriction. We show that finding vertices at distance d from a particular vertex will always take d passes, for all d ∈ 1,...,t 2 , when the space restriction is o(n1+1 t). For girth, we show the existence of a direct trade-off between space and passes in the form of a lower bound on the product of the space requirement and number of passes. Finally, we conclude with two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by at most a log factor.