More Like this

1. A Shared-Memory Parallel Algorithm for Updating Single-Source Shortest Paths in Large Dynamic Networks

   https://doi.org/10.1109/HiPC.2018.00035  

   Srinivasan, Sriram; Riazi, Sara; Norris, Boyana; Das, Sajal K.; Bhowmick, Sanjukta (December 2018, 2018 IEEE 25th International Conference on High Performance Computing (HiPC))

   Computing the single-source shortest path (SSSP) is one of the fundamental graph algorithms, and is used in many applications. Here, we focus on computing SSSP on large dynamic graphs, i.e. graphs whose structure evolves with time. We posit that instead of recomputing the SSSP for each set of changes on the dynamic graphs, it is more efficient to update the results based only on the region of change. To this end, we present a novel two-step shared-memory algorithm for updating SSSP on weighted large-scale graphs. The key idea of our algorithm is to identify changes, such as vertex/edge addition and deletion, that affect the shortest path computations and update only the parts of the graphs affected by the change. We provide the proof of correctness of our proposed algorithm. Our experiments on real and synthetic networks demonstrate that our algorithm is as much as 4X faster compared to computing SSSP with Galois, a state-of-the-art parallel graph analysis software for shared memory architectures. We also demonstrate how increasing the asynchrony can lead to even faster updates. To the best of our knowledge, this is one of the first practical parallel algorithms for updating networks on shared-memory systems, that is also scalable to large networks. 

   more » « less
2. Online Topology Inference from Streaming Stationary Graph Signals

   https://doi.org/10.1109/DSW.2019.8755560  

   Shafipour, Rasoul; Hashemi, Abolfazl; Mateos, Gonzalo; Vikalo, Haris (June 2019, 2019 IEEE Data Science Workshop (DSW))

   We address the problem of online topology inference from streaming nodal observations of graph signals generated by linear diffusion dynamics on the sought graph. To that end, we leverage the stationarity of the signals and use the so-called graph-shift operator (GSO) as a matrix representation of the graph. Under this model, estimated covariance eigenvectors obtained from streaming independent graph signals diffused on the sought network are a valid estimator of the GSO's spectral templates. We develop an ADMM algorithm to find a sparse and structurally admissible GSO given the eigenvectors estimate. Then, we propose an online scheme that upon sensing new diffused observations, efficiently updates eigenvectors (thus makes more accurate on expectation) and performs only one or a few iterations of the mentioned ADMM until the new data is observed. Numerical tests illustrate the effectiveness of the proposed topology inference approach in recovering large scale graphs, adapting to streaming information, and accommodating changes in the sought network. 

   more » « less
3. Online Network Topology Inference with Partial Connectivity Information

   https://doi.org/10.1109/CAMSAP45676.2019.9022677  

   Shafipour, Rasoul; Mateos, Gonzalo (December 2019, 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP))

   We develop algorithms for online topology inference from streaming nodal observations and partial connectivity information; i.e., a priori knowledge on the presence or absence of a few edges may be available as in the link prediction problem. The observations are modeled as stationary graph signals generated by local diffusion dynamics on the unknown network. Said stationarity assumption implies the simultaneous diagonalization of the observations' covariance matrix and the so-called graph shift operator (GSO), here the adjacency matrix of the sought graph. When the GSO eigenvectors are perfectly obtained from the ensemble covariance, we examine the structure of the feasible set of adjacency matrices and its dependency on the prior connectivity information available. In practice one can only form an empirical estimate of the covariance matrix, so we develop an alternating algorithm to find a sparse GSO given its imperfectly estimated eigenvectors. Upon sensing new diffused observations in the streaming setting, we efficiently update eigenvectors and perform only one (or a few) online iteration(s) of the proposed algorithm until a new datum is observed. Numerical tests showcase the effectiveness of the novel batch and online algorithms in recovering real-world graphs. 

   more » « less
4. A Communication-Avoiding 3D LU Factorization Algorithm for Sparse Matrices

   Sao, Piyush; Li, Xiaoye; Vuduc, Richard (May 2018, Proceedings - IEEE International Parallel and Distributed Processing Symposium)

   We propose a new algorithm to improve the strong scalability of right-looking sparse LU factorization on distributed memory systems. Our 3D sparse LU algorithm uses a three-dimensional PI process grid, aggressively exploits elimination tree parallelism and trades off increased memory for reduced per-process communication. We also analyze the asymptotic improvements for planar graphs (e.g., from 2D grid or mesh domains) and certain non-planar graphs (specifically for 3D grids and meshes). For planar graphs with n vertices, our algorithm reduces communication volume asymptotically in n by a factor of O(sqrt(logn)) and latency by a factor of O(logn). For non-planar cases, our algorithm can reduce the per-process communication volume by 3× and latency by O(n^1/3) times. In all cases, the memory needed to achieve these gains is a constant factor. We implemented our algorithm by extending the 2D data structure used in SuperLU_DIST. Our new 3D code achieves speedups up to 27× for planar graphs and up to 3.3× for non-planar graphs over the baseline 2D SuperLU_DIST when run on 24,000 cores of a Cray XC30. 

   more » « less
5. Streaming Algorithms with Few State Changes

   https://doi.org/10.1145/3651145  

   Jayaram, Rajesh; Woodruff, David P; Zhou, Samson (May 2024, Proceedings of the ACM on Management of Data)

   In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typically focuses on minimizing space and update time, these metrics fail to capture the asymmetric costs, inherent in modern hardware and database systems, of reading versus writing to memory. In fact, most streaming algorithms write to their memory on every update, which is undesirable when writing is significantly more expensive than reading. This raises the question of whether streaming algorithms with small space and number of memory writes are possible. We first demonstrate that, for the fundamental F_pmoment estimation problem with p ≥ 1, any streaming algorithm that achieves a constant factor approximation must make Ω(n^1-1/p) internal state changes, regardless of how much space it uses. Perhaps surprisingly, we show that this lower bound can be matched by an algorithm which also has near-optimal space complexity. Specifically, we give a (1+ε)-approximation algorithm for F_pmoment estimation that use a near-optimal ~O_ε(n^1-1/p) number of state changes, while simultaneously achieving near-optimal space, i.e., for p∈[1,2), our algorithm uses poly(log n,1/ε) bits of space for, while for p>2, the algorithm uses ~O_ε(n^1-1/p) space. We similarly design streaming algorithms that are simultaneously near-optimal in both space complexity and the number of state changes for the heavy-hitters problem, sparse support recovery, and entropy estimation. Our results demonstrate that an optimal number of state changes can be achieved without sacrificing space complexity. 

   more » « less