{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:55:47Z","timestamp":1757613347001,"version":"3.44.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:p>Many graph processing applications consist of read-only workloads that need to perform low-latency traversals over large graphs. These traversals are inherently expensive, and storage and processing systems need to be optimized for them. 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 the serialization layout obtained by graph ordering techniques. 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 the popular GCLOCK algorithm for input graphs with different structural properties while running various query types. Our evaluation shows that LAC can outperform GCLOCK through page fault improvements by reducing latency up to 1.42X in simulation studies and up to 1.23X with integration into the Neo4j system.<\/jats:p>","DOI":"10.14778\/3746405.3746413","type":"journal-article","created":{"date-parts":[[2025,9,3]],"date-time":"2025-09-03T17:06:20Z","timestamp":1756919180000},"page":"2859-2871","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Locality-Aware Cache Replacement Policy for Graph Traversals"],"prefix":"10.14778","volume":"18","author":[{"given":"Zeynep","family":"Korkmaz","sequence":"first","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Tamer","family":"\u00d6zsu","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Khuzaima","family":"Daudjee","sequence":"additional","affiliation":[{"name":"University of Waterloo, Waterloo, ON, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,9,3]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[n. d.]. Graph Data Platform | Graph Database Management System | Neo4j. https:\/\/neo4j.com\/"},{"key":"e_1_2_1_2_1","volume-title":"Graph Aware Caching Policy for Distributed Graph Stores. In IEEE Int. Conf on Cloud Engineering. 6\u201315","author":"Aksu Hidayet","year":"2015","unstructured":"Hidayet Aksu, Mustafa Canim, Yuan-Chi Chang, Ibrahim Korpeoglu, and Ozgur Ulusoy. 2015. Graph Aware Caching Policy for Distributed Graph Stores. In IEEE Int. Conf on Cloud Engineering. 6\u201315."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 4th Annual Symposium on Combinatorial Search.","author":"Bakhshandeh Reza","year":"2011","unstructured":"Reza Bakhshandeh, Mehdi Samadi, Zohreh Azimifar, and Jonathan Schaeffer. 2011. Degrees of Separation in Social Networks. Proceedings of the 4th Annual Symposium on Combinatorial Search."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/645484.656550"},{"key":"e_1_2_1_6_1","volume-title":"Proc. USENIX 2013 Annual Technical Conf. 49\u201360","author":"Bronson Nathan","year":"2013","unstructured":"Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. 2013. TAO: Facebook's distributed data store for the social graph. In Proc. USENIX 2013 Annual Technical Conf. 49\u201360."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648179"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2742786"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.48550\/arxiv.2001.08448"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/HPCA47549.2020.00028"},{"key":"e_1_2_1_11_1","unstructured":"Xiyang Feng Guodong Jin Ziyi Chen Chang Liu and Semih Saliho\u011flu. 2022. K\u00f9zu Database Management System Source Code. https:\/\/github.com\/kuzudb\/kuzu"},{"key":"e_1_2_1_12_1","volume-title":"Proc. 13th Biennial Conf. on Innovative Data Systems Research.","author":"Feng Xiyang","year":"2023","unstructured":"Xiyang Feng, Guodong Jin, Ziyi Chen, Chang Liu, and Semih Saliho\u011flu. 2023. K\u00f9zu Graph Database Management System. In Proc. 13th Biennial Conf. on Innovative Data Systems Research."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487581"},{"key":"e_1_2_1_14_1","unstructured":"Nicolaus Henke Jacques Bughin Michael Chui J. Manyika Tamim Saleh and Bill Wiseman. 2016. The Age of Analytics: Competing in a data-driven world. https:\/\/api.semanticscholar.org\/CorpusID:196173558"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/MIC.2012.40"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1815961.1815971"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/305219.305248"},{"key":"e_1_2_1_18_1","volume-title":"Proc. 10th USENIX Symp. on Operating System Design and Implementation. 31\u201346","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: large-scale graph computation on just a PC. In Proc. 10th USENIX Symp. on Operating System Design and Implementation. 31\u201346."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/149439.133084"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/2482626.2482663"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Elizabeth J. O'Neil Patrick E. O'Neil and Gerhard Weikum. 1993. The LRU-K page replacement algorithm for database disk buffering. ACM SIGMOD Rec. (1993).","DOI":"10.1145\/170035.170081"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654928"},{"issue":"3","key":"e_1_2_1_23_1","article-title":"Experiments on the minimum linear arrangement problem","volume":"2","author":"Petit Jordi","year":"2004","unstructured":"Jordi Petit. 2004. Experiments on the minimum linear arrangement problem. ACM J. Exp. Algorithmics 8, Article 2.3 (2004).","journal-title":"ACM J. Exp. Algorithmics 8, Article"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Ira Pohl. 1969. Bi-directional and heuristic search in path problems. https:\\\/\/api.semanticscholar.org\/CorpusID:61081057","DOI":"10.2172\/1453875"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/320263.320276"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3626246.3654757"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915220"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556581"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-017-7191-3"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.future.2020.03.015"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137831"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8257937"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2503210.2503225"},{"key":"e_1_2_1_36_1","volume-title":"Szalay","author":"Zheng Da","year":"2015","unstructured":"Da Zheng, Disa Mhembere, Randal Burns, Joshua Vogelstein, Carey E. Priebe, and Alexander S. Szalay. 2015. FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs. In Proc. 13th USENIX Conf. on File and Storage Technologies. USENIX Association, 45\u201358."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_15"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3746405.3746413","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T19:52:17Z","timestamp":1757015537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3746405.3746413"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5]]},"references-count":37,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["10.14778\/3746405.3746413"],"URL":"https:\/\/doi.org\/10.14778\/3746405.3746413","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,5]]},"assertion":[{"value":"2025-09-03","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}