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

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

For a directed graph G with n vertices and a start vertex ustart, we wish to (approximately) sample an L-step random walk over G starting from ustart with minimum space using an algorithm that only makes few passes over the edges of the graph. This problem found many applications, for instance, in approximating the PageRank of a webpage. If only a single pass is allowed, the space complexity of this problem was shown to be Θ(n · L). Prior to our work, a better space complexity was only known with Õ(√L) passes. We essentially settle the space complexity of this random walk simulation problem for two-pass streaming algorithms, showing that it is Θ(n · √L), by giving almost matching upper and lower bounds. Our lower bound argument extends to every constant number of passes p, and shows that any p-pass algorithm for this problem uses Ω(n · L1/p) space. In addition, we show a similar Θ(n · √L) bound on the space complexity of any algorithm (with any number of passes) for the related problem of sampling an L-step random walk from every vertex in the graph.

Original languageEnglish (US)
Title of host publication48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
EditorsNikhil Bansal, Emanuela Merelli, James Worrell
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771955
DOIs
StatePublished - Jul 1 2021
Event48th International Colloquium on Automata, Languages, and Programming, ICALP 2021 - Virtual, Glasgow, United Kingdom
Duration: Jul 12 2021Jul 16 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume198
ISSN (Print)1868-8969

Conference

Conference48th International Colloquium on Automata, Languages, and Programming, ICALP 2021
Country/TerritoryUnited Kingdom
CityVirtual, Glasgow
Period7/12/217/16/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Random walk sampling
  • Streaming algorithms

Fingerprint

Dive into the research topics of 'Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs'. Together they form a unique fingerprint.

Cite this