English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

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 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. MIT. lijieche@mit.edu Princeton University. gillat.kol@gmail.com Princeton University. dp20@princeton.edu Princeton University. rrsaxena@princeton.edu Institute for Advanced Study. zhaos@ias.edu Princeton University. yuhch123@gmail.com

Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs