License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.46
URN: urn:nbn:de:0030-drops-101399
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10139/
Go to the corresponding LIPIcs Volume Portal

Jin, Ce

Simulating Random Walks on Graphs in the Streaming Model

pdf-format:
LIPIcs-ITCS-2019-46.pdf (0.5 MB)

Abstract

We study the problem of approximately simulating a t-step random walk on a graph where the input edges come from a single-pass stream. The straightforward algorithm using reservoir sampling needs O(nt) words of memory. We show that this space complexity is near-optimal for directed graphs. For undirected graphs, we prove an Omega(n sqrt{t})-bit space lower bound, and give a near-optimal algorithm using O(n sqrt{t}) words of space with 2^{-Omega(sqrt{t})} simulation error (defined as the l_1-distance between the output distribution of the simulation algorithm and the distribution of perfect random walks). We also discuss extending the algorithms to the turnstile model, where both insertion and deletion of edges can appear in the input stream.

BibTeX - Entry

@InProceedings{jin:LIPIcs:2018:10139,
  author =	{Ce Jin},
  title =	{{Simulating Random Walks on Graphs in the Streaming Model}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{46:1--46:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10139},
  URN =		{urn:nbn:de:0030-drops-101399},
  doi =		{10.4230/LIPIcs.ITCS.2019.46},
  annote =	{Keywords: streaming models, random walks, sampling}
}

Keywords: streaming models, random walks, sampling
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI