PhD Seminar • Data Systems • LAC: Locality-Aware Cache Replacement Policy for Graphs

Please note: This PhD seminar will take place in DC 2585 (NOTE NEW ROOM).

Zeynep Korkmaz, PhD candidate
David R. Cheriton School of Computer Science

Supervisors: Professors M. Tamer Özsu, Khuzaima Daudjee

Most graph processing applications consist of read-intensive workloads which need to perform low-latency traversals over large graphs. These traversals are inherently expensive. Storage and processing systems need to be optimized for them. The performance and scalability of current graph DBMSs have been an active area of research and development. The performance of secondary storage-based systems can be improved by caching locality-driven data in memory. Exploring the data reuse of graph objects in applications is important to decrease the page faults in the cache. However, graph applications can suffer from poor access locality, making caching of graph data challenging. Locality can be imposed through graph ordering algorithms that can be exploited by cache replacement algorithms.

We propose a graph locality-aware cache replacement policy called LAC that exploits serialization layout obtained by a state-of-the-art graph ordering technique. We show that the spatial locality that is captured on disk pages offers temporal locality for subsequent accesses of cache pages, and this information can be used to make improved cache replacement decisions. We evaluate LAC against its competitor for the input graphs with different structural properties while running various query types. Simulation studies of LAC show that LAC can outperform the competitor policy and achieve page fault improvements by up to 1.6 times while reducing query latency.