  Graphs in many applications, such as social networks and IoT, are inherently
streaming, involving continuous additions and deletions of vertices and edges
at high rates. Constructing random walks in a graph, i.e., sequences of
vertices selected with a specific probability distribution, is a prominent task
in many of these graph applications as well as machine learning (ML) on
graph-structured data. In a streaming scenario, random walks need to constantly
keep up with the graph updates to avoid stale walks and thus, performance
degradation in the downstream tasks. We present Wharf, a system that
efficiently stores and updates random walks on streaming graphs. It avoids a
potential size explosion by maintaining a compressed, high-throughput, and
low-latency data structure. It achieves (i) the succinct representation by
coupling compressed purely functional binary trees and pairing functions for
storing the walks, and (ii) efficient walk updates by effectively pruning the
walk search space. We evaluate Wharf, with real and synthetic graphs, in terms
of throughput and latency when updating random walks. The results show the high
superiority of Wharf over inverted index- and tree-based baselines.
