  Personalized PageRank (PPR) is a critical measure of the importance of a node
t to a source node s in a graph. The Single-Source PPR (SSPPR) query computes
the PPR's of all the nodes with respect to s on a directed graph $G$ with $n$
nodes and $m$ edges, and it is an essential operation widely used in graph
applications. In this paper, we propose novel algorithms for solving two
variants of SSPPR: (i) high-precision queries and (ii) approximate queries. For
high-precision queries, Power Iteration (PowItr) and Forward Push (FwdPush) are
two fundamental approaches. Given an absolute error threshold $\lambda$, the
only known bound of FwdPush is $O(\frac{m}{\lambda})$, much worse than the $O(m
\log \frac{1}{\lambda})$-bound of PowItr. Whether FwdPush can achieve the same
running time bound as PowItr does still remains an open question in the
research community. We give a positive answer to this question by showing that
the running time of a common implementation of FwdPush is actually bounded by
$O(m \cdot \log \frac{1}{\lambda})$.Based on this finding, we propose a new
algorithm, called Power Iteration with Forward Push (PowerPush), which
incorporates the strengths of both PowItr and FwdPush. For approximate queries
(with a relative error $\epsilon$), we propose a new algorithm, called
SpeedPPR, with overall expected time bounded by $O(n \cdot \log n \cdot \log
\frac{1}{\epsilon})$ on scale-free graphs. This bound greatly improves the
$O(\frac{n \cdot \log n}{\epsilon})$ bound of a state-of-the-art algorithm
FORA.
