Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs

DOI10.4230/LIPICS.ICALP.2021.52MaRDI QIDQ7241150zbMATH OpenFDO

Authors Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.52

zbMATH Keywords

streaming algorithmsrandom walk sampling

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 2086663 (Why is no real title available?)
• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• scientific article; zbMATH DE number 7559089 (Why is no real title available?)
• scientific article; zbMATH DE number 7053293 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
• An almost-linear time algorithm for uniform random spanning tree generation
• Approximating the Permanent
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Automata, Languages and Programming
• Better bounds for matchings in the streaming model
• Better streaming algorithms for clustering problems
• Computing exact minimum cuts without knowing the graph
• Estimating PageRank on graph streams
• Finding sparse cuts locally using evolving sets
• Graph Distances in the Data-Stream Model
• Improved massively parallel computation algorithms for MIS, matching, and vertex cover
• Incidence geometries and the pass complexity of semi-streaming set cover
• Independent sets in vertex-arrival streams
• Intractability of min- and max-cut in streaming graphs
• Perfect L_p sampling in a data stream
• Random generation of combinatorial structures from a uniform distribution
• Random sampling with a reservoir
• Semi-streaming set cover (extended abstract)
• Sublinear algorithms for ( + 1) vertex coloring
• Superlinear lower bounds for multipass graph processing
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• Tight bounds for single-pass streaming complexity of the set cover problem
• Undirected connectivity in log-space
• Using PageRank to Locally Partition a Graph
• Vertex Ordering Problems in Directed Graph Streams
• Weighted Matchings via Unweighted Augmentations
• Weighted min-cut: sequential, cut-query, and streaming algorithms
• Weighted sums of certain dependent random variables

Cited in

(1)

• New algorithms and lower bounds for streaming tournaments

This page was built for publication: Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7241150)