publication . Preprint . Conference object . Article . 2014

Single Pass Spectral Sparsification in Dynamic Streams

M. Kapralov; Y. T. Lee; C. N. Musco; C. P. Musco; A. Sidford;
Open Access English
  • Published: 04 Jul 2014
Abstract
We present the first single pass algorithm for computing spectral sparsifiers of graphs in the dynamic semi-streaming model. Given a single pass over a stream containing insertions and deletions of edges to a graph G, our algorithm maintains a randomized linear sketch of the incidence matrix of G into dimension O((1/epsilon^2) n polylog(n)). Using this sketch, at any point, the algorithm can output a (1 +/- epsilon) spectral sparsifier for G with high probability. While O((1/epsilon^2) n polylog(n)) space algorithms are known for computing "cut sparsifiers" in dynamic streams [AGM12b, GKP12] and spectral sparsifiers in "insertion-only" streams [KL11], prior to o...
Subjects
arXiv: Computer Science::Data Structures and Algorithms
free text keywords: Computer Science - Data Structures and Algorithms, Discrete mathematics, Dimensionality reduction, Incidence matrix, Sparse matrix, Sampling (statistics), Arbitrary-precision arithmetic, Matrix (mathematics), Row, Approximation algorithm, Combinatorics, Mathematics, General Computer Science, General Mathematics, Graph, Single pass
Funded by
NSF| CAREER: Geometric Techniques for Algorithm Design
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0843915
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| Emerging Frontiers of Science of Information
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 0939370
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| AF: Medium: Taming Masssive Data with Sub-Linear Algorithms
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1065125
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations
,
NSF| Graduate Research Fellowship Program
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1122374
  • Funding stream: Directorate for Education & Human Resources | Division of Graduate Education
,
NSF| AF: Small: Bounded-Contention Coding for Wireless Networks
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1217506
  • Funding stream: Directorate for Computer & Information Science & Engineering | Division of Computing and Communication Foundations

In ICALP (2), pages 328-338, 2009.

[AGM12a] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Analyzing graph structure via linear measurements. In SODA, pages 459-467, 2012.

[AGM12b] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In PODS, pages 5-14, 2012.

[AGM13] Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Spectral sparsification in dynamic graph streams. In APPROX-RANDOM, pages 1-10, 2013.

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . Conference object . Article . 2014

Single Pass Spectral Sparsification in Dynamic Streams

M. Kapralov; Y. T. Lee; C. N. Musco; C. P. Musco; A. Sidford;