Adaptive optimization techniques in graph-based applications

Abstract

Performance optimization is one of the central problems in data systems because the systems are facing heavy computation workloads. For example, taxi-hailing services (e.g., Uber) require powerful database systems to process massive volumes of operations (e.g., kNN queries, location updates) efficiently; user-ranking services in Tencent involves millions of Personalized PageRank (PPR) queries on billion-edge social networks.

In performance optimization, we have to take into account the variation of the application features. For example, the query/update workloads vary in taxi-hailing services, as the workloads depend on the scales of the services and the diversities of the cities that deploy the services. From the perspective of database solutions, it is desirable to have a solution that can be well adapted to different workloads, or has the workload adaptability.

Further, the system hardware to deploy the service can change from time to time. As a location-based service expands and scales, its system needs to be upgraded to more powerful machines (e.g., one with many CPU cores). To effectively optimize the performance, a good database solution should be able to exploit the full potential of high-performance hardware with minimum engineering efforts. In other words, it is interesting to design a solution that has good system adaptability.

In addition, the workloads also change with the given requirements on the application. Take the task of approximating PPRs as an example, we often require that the estimations should be within e relative errors. A natural question is, whether the computation optimization should be dependent on e? This question motivates us to design an approach that possesses the accuracy-requirement adaptability.

In this thesis we investigate the adaptive approaches considering the aforementioned adaptabilities, and examine their effectiveness in performance optimization for graph-based applications. We focus on representative graph-based applications including 1) the kNN problem that is applied in location-based services and 2) the batch PPR processing that is applied in ranking services. Based on these two problems, we design three adaptive approaches which are respectively associated with the workload adaptability, system adaptability and requirement adaptability. Our studies strongly argue that, adaptive approaches are beneficial to the performance optimizations in the graph-based applications we study.