Random Walk with Restart (abbreviated as RWR) has been widely employed in Web search and recommendation systems and several performance enhancement approaches for RWR have been proposed to save storage costs and improve the on-line response time. In this paper, we explore and implement RWR for query recommendation in Yahoo! Asia Knowledge Plus, which contains a huge amount of Question and Answer Web pages (abbreviated as QA). From user click logs, we first discover temporal following patterns that indicates frequent QA browsing behaviors of users within a pre-defined time window. In light of temporal following patterns, a graph structure is built for RWR. Since users may submit their queries at the same time, we design a parallel approach for the implementation of RWR in a cloud computing environment. Empirical results on Yahoo! Asia Knowledge Plus dataset demonstrates that our RWR-based recommendation is able to effectively and efficiently recommend related QA Web pages.