Personalized PageRanks over Dynamic Graphs - The Case for Optimizing Quality of Service

We study the problem of Quality-of-Service (QoS)-Aware Personalized PageRank (PPR) computation. Existing studies mostly focus on improving the PPR query processing time. However, the query processing time alone may not reflect the service quality in real-world PPR-based systems. The query response time can be a more service-relevant measure in many applications such as the online game service of Tencent and the related-pin recommendation module of Pinterest. We make the first attempt at studying QoS-Aware PPR computation and present Quota, a system that adapts the state-of-the-art PPR algorithms to a given environment for minimizing query response time. Equipped with mathematical tools including queuing theory, algorithmic complexity analysis, and constrained optimization, Quota is designed to adapt itself to a wide spectrum of workloads. We conduct extensive experiments on real datasets and show that Quota can reduce the query response time compared with state-of-the-art PPR algorithms, often by a significant margin.