More Web Proxy on the site http://driver.im/

article

On graph problems in a semi-streaming model

Authors:

Joan Feigenbaum,

Sampath Kannan,

Andrew McGregor,

Siddharth Suri,

Jian ZhangAuthors Info & Claims

Theoretical Computer Science, Volume 348, Issue 2

Pages 207 - 216

https://doi.org/10.1016/j.tcs.2005.09.013

Published: 08 December 2005 Publication History

Abstract

We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G = (V, E), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O(n ċ polylog n), where n = |V|. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithmic improvement for the bipartite case. We also exhibit log n/log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω(log^(1-ε) n) lower bounds.

References

[1]

{1} J. Abello, A.L. Buchsbaum, J.R. Westbrook, A functional approach to external graph algorithms, Algorithmica 32 (3) (2002) 437-458.

Digital Library

[2]

{2} N. Alon, Y. Matias, M. Szegedy, The space complexity of approximating the frequency moments, J. Comput. Systems Sci. 58 (1) (1999) 137-147.

Digital Library

[3]

{3} I. Althöfer, G. Das, D. Dobkin, D. Joseph, Generating sparse spanners for weighted graphs, in: Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science, Vol. 447, Springer, Berlin, 1990, pp. 26-37.

Digital Library

[4]

{4} Z. Bar-Yossef, R. Kumar, D. Sivakumar, Reductions in streaming algorithms, with an application to counting triangles in graphs, in: Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 2002, pp. 623-632.

Digital Library

[5]

{5} B. Bollobás, Extremal Graph Theory, Academic Press, New York, 1978.

Digital Library

[6]

{6} A.L. Buchsbaum, R. Giancarlo, J.R. Westbrook, On finding common neighborhoods in massive graphs, Theoretical Comput. Sci. 299 (1-3) (2003) 707-718.

Digital Library

[7]

{7} E. Cohen, Fast algorithms for constructing t-spanners and paths with stretch t, SIAM J. Comput. 28 (1998) 210-236.

Digital Library

[8]

{8} P. Drineas, R. Kannan, Pass efficient algorithms for approximating large matrices, in: Proc. 14th ACM-SIAM Symp. on Discrete Algorithms, 2003, pp. 223-232.

Digital Library

[9]

{9} D. Eppstein, Z. Galil, G.F. Italiano, Dynamic graph algorithms, in: Handbook of Algorithms and Theory of Computation, CRC Press, Boca Raton, FL, 1999(Chapter 8).

[10]

{10} J. Feigenbaum, S. Kannan, M. Strauss, M. Viswanathan, An approximate L ¹ difference algorithm for massive data streams, SIAM J. Comput. 32 (1) (2002) 131-151.

Digital Library

[11]

{11} P. Flajolet, G.N. Martin, Probabilistic counting, in: Proc. 24th IEEE Symp. on Foundation of Computer Science, 1983, pp. 76-82.

[12]

{12} A.C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, M. Strauss, Fast, small-space algorithms for approximate histogram maintenance, in: Proc. 34th ACM Symp.on Theory of Computing, 2002, pp. 389-398.

Digital Library

[13]

{13} S. Guha, N. Koudas, K. Shim, Data-streams and histograms, in: Proc. 33rd ACM Symp. on Theory of Computing, 2001, pp. 471-475.

Digital Library

[14]

{14} M.R. Henzinger, P. Raghavan, S. Rajagopalan, Computing on data streams, Technical Report 1998-001, DEC Systems Research Center, 1998.

[15]

{15} P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, in: Proc. 41st IEEE Symp. on Foundations of Computer Science, 2000, pp. 189-197.

Digital Library

[16]

{16} B. Kalyanasundaram, G. Schnitger, The probabilistic communication complexity of set intersection, SIAM J. Discrete Math. 5 (1990) 545-557.

Digital Library

[17]

{17} M. Karpinski, W. Rytter, Fast Parallel Algorithms for Graph Matching Problems, Oxford Lecture Series in Mathematics and its Applications, Oxford University Press, Oxford, 1998.

Digital Library

[18]

{18} R. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Extracting large-scale knowledge bases from the web, in: Proc. 25th Internat. Conf. on Very Large Data Bases, 1999, pp. 639-650.

Digital Library

[19]

{19} S. Muthukrishnan, Data streams: algorithms and applications, 2003, Available at http://athos.rutgers.edu/~muthu/stream-1-1.ps

[20]

{20} R. Tarjan, Data Structures and Network Algorithms, SIAM, Philadelphia, PA, 1983.

Digital Library

[21]

{21} R. Uehara, Z.-Z. Chen, Parallel approximation algorithms for maximum weighted matching in general graphs, Inform. Process. Lett. 76 (1-2) (2000) 13-17.

Digital Library

Cited By

Bhattacharya SKiss PSaranurak TWajc D(2024)Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update TimeJournal of the ACM10.1145/367900971:5(1-32)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3679009
Czumaj AMishra GMukherjee AKuznetsov PGelles ROlivetti D(2024)Streaming Graph Algorithms in the Massively Parallel Computation ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662770(496-507)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662770
Tench DWest EZhang VBender MChowdhury ADelayo DDellas JFarach-Colton MSeip TZhang K(2024)GraphZeppelin: How to Find Connected Components (Even When Graphs Are Dense, Dynamic, and Massive)ACM Transactions on Database Systems10.1145/364384649:3(1-31)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1145/3643846
Show More Cited By

Index Terms

On graph problems in a semi-streaming model
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
  2. Mathematical analysis
    1. Functional analysis
      1. Approximation
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
  2. Randomness, geometry and discrete structures

Recommendations

Deterministic (1+𝜀)-approximate maximum matching with poly(1/𝜀) passes in the semi-streaming model and beyond
STOC 2022: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing

We present a deterministic (1+ε)-approximate maximum matching algorithm in poly(1/ε) passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on 1/ε. Our algorithm exponentially ...
Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Efficient algorithms for constructing (1+∊,β)-spanners in the distributed and streaming models
Abstract
For an unweighted undirected graph G = (V,E), and a pair of positive integers α ≥ 1, β ≥ 0, a subgraph G′ = (V,H), H ⊂eqE, is called an (α,β)-spanner of G if for every pair of vertices u,v ∊ V, dist_G′(u,v) ≤ α ⋅ dist_G(u,v) + β.
It was shown in [21] ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science

Theoretical Computer Science Volume 348, Issue 2

Automata, languages and programming: Algorithms and complexity (ICALP-A 2004)

8 December 2005

237 pages

ISSN:0304-3975

Issue’s Table of Contents

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 08 December 2005

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

118
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bhattacharya SKiss PSaranurak TWajc D(2024)Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update TimeJournal of the ACM10.1145/367900971:5(1-32)Online publication date: 23-Jul-2024
https://dl.acm.org/doi/10.1145/3679009
Czumaj AMishra GMukherjee AKuznetsov PGelles ROlivetti D(2024)Streaming Graph Algorithms in the Massively Parallel Computation ModelProceedings of the 43rd ACM Symposium on Principles of Distributed Computing10.1145/3662158.3662770(496-507)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3662158.3662770
Tench DWest EZhang VBender MChowdhury ADelayo DDellas JFarach-Colton MSeip TZhang K(2024)GraphZeppelin: How to Find Connected Components (Even When Graphs Are Dense, Dynamic, and Massive)ACM Transactions on Database Systems10.1145/364384649:3(1-31)Online publication date: 16-May-2024
https://dl.acm.org/doi/10.1145/3643846
Assadi SKonrad CNaidu KSundaresan JMohar BShinkar IO'Donnell R(2024)O(log log n) Passes Is Optimal for Semi-streaming Maximal Independent SetProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649763(847-858)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649763
Assadi SKol GZhang ZMohar BShinkar IO'Donnell R(2024)Optimal Multi-pass Lower Bounds for MST in Dynamic StreamsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649755(835-846)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649755
Huang CSellier F(2024)Semi-streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid ConstraintsAlgorithmica10.1007/s00453-024-01272-x86:11(3598-3628)Online publication date: 14-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01272-x
Oostveen Jvan Leeuwen E(2024)Parameterized Complexity of Streaming Diameter and Connectivity ProblemsAlgorithmica10.1007/s00453-024-01246-z86:9(2885-2928)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s00453-024-01246-z
Feldman MSzarf A(2024)Maximum Matching Sans Maximal Matching: A New Approach for Finding Maximum Matchings in the Data Stream ModelAlgorithmica10.1007/s00453-023-01190-486:4(1173-1209)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.1007/s00453-023-01190-4
Bernstein A(2024)Improved Bounds for Matching in Random-Order StreamsTheory of Computing Systems10.1007/s00224-023-10155-768:4(758-772)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s00224-023-10155-7
Chakrabarty SMakarychev KOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Single-pass pivot algorithm for correlation clustering. keep it simple!Proceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666402(6412-6421)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666402
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents