{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T17:28:07Z","timestamp":1786987687403,"version":"build-2736575974"},"reference-count":51,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T00:00:00Z","timestamp":1786924800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["CUHK14208521"],"award-info":[{"award-number":["CUHK14208521"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Storage"],"published-print":{"date-parts":[[2026,12,30]]},"abstract":"<jats:p>The All-Distances Sketch (ADS) is a powerful and theoretically-sound sketching scheme that captures neighborhood information in graphs for approximate processing. It enables high-accuracy estimation of many useful applications with a guarantee of accuracy and can significantly accelerate the execution times by orders of magnitude. However, ADS requires a substantial amount of space, that is, multiple times larger than the graph data. More seriously, existing studies mainly focus on managing ADSs in memory, posing an increasing challenge for users who aim to leverage ADS for large-scale graph processing, particularly in light of the exponential growth of real-world graphs nowadays.<\/jats:p>\n                  <jats:p>\n                    To this end, this article introduces Oasis, an\n                    <jats:underline>O<\/jats:underline>\n                    ut-of-core\n                    <jats:underline>A<\/jats:underline>\n                    pproximate graph\n                    <jats:underline>SYS<\/jats:underline>\n                    tem that brings the ADS technique into practical use by leveraging storage effectively. Specifically, Oasis offers a holistic framework that facilitates both ADS construction and estimation. For ADS construction, it allows users to adjust the memory usage based on the machine\u2019s available memory and enable an efficient construction process. For ADS estimation, Oasis provides a user-friendly interface to easily execute the estimators while mitigating the impact of slow storage I\/O. Evaluation results show that Oasis provides a practical graph processing solution with exceptional execution time and low memory usage, at the cost of a slight decrease in accuracy.\n                  <\/jats:p>","DOI":"10.1145\/3813113","type":"journal-article","created":{"date-parts":[[2026,5,8]],"date-time":"2026-05-08T10:58:07Z","timestamp":1778237887000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Enabling Cost-effective and Efficient All-Distance Sketching in Out-of-core Approximate Graph System"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8992-480X","authenticated-orcid":false,"given":"Tsun-Yu","family":"Yang","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong","place":["Hong Kong, Hong Kong"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8226-6856","authenticated-orcid":false,"given":"Yizou","family":"Chen","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong","place":["Hong Kong, Hong Kong"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1909-6239","authenticated-orcid":false,"given":"Yi","family":"Li","sequence":"additional","affiliation":[{"name":"The University of Texas at Dallas","place":["Richardson, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5815-9706","authenticated-orcid":false,"given":"Bingzhe","family":"Li","sequence":"additional","affiliation":[{"name":"Computer Science, The University of Texas at Dallas","place":["Richardson, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4029-757X","authenticated-orcid":false,"given":"Ming-Chang","family":"Yang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong","place":["Hong Kong, Hong Kong"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,8,17]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939762"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150412"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963493"},{"key":"e_1_3_1_6_2","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1145\/988672.988752","volume-title":"Proceedings of the 13th International World Wide Web Conference (WWW 2004)","author":"Boldi Paolo","year":"2004","unstructured":"Paolo Boldi and Sebastiano Vigna. 2004. The WebGraph framework I: Compression techniques. In Proceedings of the 13th International World Wide Web Conference (WWW 2004). ACM Press, Manhattan, USA, 595\u2013601."},{"key":"e_1_3_1_7_2","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1145\/2896377.2901458","volume-title":"Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science","author":"Buchnik Eliav","year":"2016","unstructured":"Eliav Buchnik and Edith Cohen. 2016. Reverse ranking by graph structure: Model and scalable algorithms. In Proceedings of the 2016 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Science. 51\u201362."},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.118"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2022.3218885"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.14778\/3632093.3632106"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1534"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/2594538.2594546","volume-title":"Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems","author":"Cohen Edith","year":"2014","unstructured":"Edith Cohen. 2014. All-distances sketches, revisited: HIP estimators for massive graphs analysis. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems. 88\u201399."},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512944"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2662077"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_3_1_16_2","unstructured":"Twitter dataset from WebGraph.2010. Retrieved from http:\/\/law.di.unimi.it\/webdata\/twitter-2010\/"},{"key":"e_1_3_1_17_2","first-page":"3147","article-title":"Scalable influence estimation in continuous-time diffusion networks","volume":"26","author":"Du Nan","year":"2013","unstructured":"Nan Du, Le Song, Manuel Gomez Rodriguez, and Hongyuan Zha. 2013. Scalable influence estimation in continuous-time diffusion networks. Advances in Neural Information Processing Systems 26 (2013), 3147\u20133155.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3323298.3323327"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_3_1_20_2","first-page":"745","volume-title":"13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18)","author":"Iyer Anand Padmanabha","year":"2018","unstructured":"Anand Padmanabha Iyer, Zaoxing Liu, Xin Jin, Shivaram Venkataraman, Vladimir Braverman, and Ion Stoica. 2018. ASAP: Fast, approximate graph pattern mining at scale. In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18). USENIX Association, Carlsbad, CA, 745\u2013761. Retrieved from https:\/\/www.usenix.org\/conference\/osdi18\/presentation\/iyer"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3210259.3210269"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3313726"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00046"},{"key":"e_1_3_1_24_2","first-page":"31","volume-title":"10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)","author":"Kyrola Aapo","year":"2012","unstructured":"Aapo Kyrola, Guy Blelloch, and Carlos Guestrin. 2012. GraphChi: Large-scale graph computation on just a PC. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). USENIX Association, Hollywood, CA, 31\u201346. Retrieved from https:\/\/www.usenix.org\/conference\/osdi12\/technical-sessions\/presentation\/kyrola"},{"key":"e_1_3_1_25_2","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384268"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2024.3510532"},{"key":"e_1_3_1_29_2","first-page":"285","volume-title":"Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST 17)","author":"Liu Hang","year":"2017","unstructured":"Hang Liu and H. Howie Huang. 2017. Graphene: Fine-grained IO management for graph computing. In Proceedings of the 15th USENIX Conference on File and Storage Technologies (FAST 17). USENIX Association, Santa Clara, CA, 285\u2013300. Retrieved from https:\/\/www.usenix.org\/conference\/fast17\/technical-sessions\/presentation\/liu"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3588725"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505760"},{"key":"e_1_3_1_32_2","first-page":"81","volume-title":"Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Palmer Christopher R.","year":"2002","unstructured":"Christopher R. Palmer, Phillip B. Gibbons, and Christos Faloutsos. 2002. ANF: A fast and scalable tool for data mining in massive graphs. In Proceedings of the 8th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 81\u201390."},{"key":"e_1_3_1_33_2","article-title":"Reciprocal recommender systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation","author":"Palomares Iv\u00e1n","year":"2021","unstructured":"Iv\u00e1n Palomares, Carlos Porcel, Luiz Pizzato, Ido Guy, and Enrique Herrera-Viedma. 2021. Reciprocal recommender systems: Analysis of state-of-art literature, challenges and opportunities towards social recommendation. Information Fusion 69 (May 2021), 103\u2013127.","journal-title":"Information Fusion"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2517349.2522740"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3128571"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2015.8"},{"key":"e_1_3_1_38_2","unstructured":"Samsung 970 PRO SSD.2018. Retrieved from https:\/\/www.samsung.com\/semiconductor\/minisite\/ssd\/product\/consumer\/970pro\/"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1002\/widm.1256"},{"key":"e_1_3_1_40_2","volume-title":"Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations","volume":"1","author":"Takac Lubos","year":"2012","unstructured":"Lubos Takac and Michal Zabovsky. 2012. Data analysis in public social networks. In Proceedings of the International Scientific Conference and International Workshop Present Day Trends of Innovations, Vol. 1."},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_3_1_42_2","first-page":"429","volume-title":"Proceedings of the 2019 USENIX Annual Technical Conference (USENIX ATC 19)","author":"Vora Keval","year":"2019","unstructured":"Keval Vora. 2019. LUMOS: Dependency-driven disk-based graph processing. In Proceedings of the 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, 429\u2013442. Retrieved from https:\/\/www.usenix.org\/conference\/atc19\/presentation\/vora"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_3_1_44_2","doi-asserted-by":"publisher","DOI":"10.1086\/210318"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/1281192.1281280"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453934"},{"key":"e_1_3_1_47_2","first-page":"373","volume-title":"Proceedings of the 22nd USENIX Conference on File and Storage Technologies (FAST 24)","author":"Yang Tsun-Yu","year":"2024","unstructured":"Tsun-Yu Yang, Yizou Chen, Yuhong Liang, and Ming-Chang Yang. 2024. Seraph: Towards scalable and efficient fully-external graph computation via on-demand processing. In Proceedings of the 22nd USENIX Conference on File and Storage Technologies (FAST 24). USENIX Association, Santa Clara, CA, 373\u2013387. Retrieved from https:\/\/www.usenix.org\/conference\/fast24\/presentation\/yang-tsun-yu"},{"key":"e_1_3_1_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3701037"},{"key":"e_1_3_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3620665.3640409"},{"key":"e_1_3_1_50_2","first-page":"45","volume-title":"Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST 15)","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 Proceedings of the 13th USENIX Conference on File and Storage Technologies (FAST 15). USENIX Association, Santa Clara, CA, 45\u201358. Retrieved from https:\/\/www.usenix.org\/conference\/fast15\/technical-sessions\/presentation\/zheng"},{"key":"e_1_3_1_51_2","first-page":"375","volume-title":"Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC 15)","author":"Zhu Xiaowei","year":"2015","unstructured":"Xiaowei Zhu, Wentao Han, and Wenguang Chen. 2015. GridGraph: Large-scale graph processing on a single machine using 2-level hierarchical partitioning. In Proceedings of the 2015 USENIX Annual Technical Conference (USENIX ATC 15). USENIX Association, Santa Clara, CA, 375\u2013386. Retrieved from https:\/\/www.usenix.org\/conference\/atc15\/technical-session\/presentation\/zhu"},{"key":"e_1_3_1_52_2","first-page":"1013","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23)","author":"Zhu Zeying","year":"2023","unstructured":"Zeying Zhu, Kan Wu, and Zaoxing Liu. 2023. Arya: Arbitrary graph pattern mining with decomposition-based sampling. In 20th USENIX Symposium on Networked Systems Design and Implementation (NSDI 23). USENIX Association, Boston, MA, 1013\u20131030. Retrieved from https:\/\/www.usenix.org\/conference\/nsdi23\/presentation\/zhu"}],"container-title":["ACM Transactions on Storage"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3813113","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T16:40:10Z","timestamp":1786984810000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3813113"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,17]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12,30]]}},"alternative-id":["10.1145\/3813113"],"URL":"https:\/\/doi.org\/10.1145\/3813113","relation":{},"ISSN":["1553-3077","1553-3093"],"issn-type":[{"value":"1553-3077","type":"print"},{"value":"1553-3093","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,17]]},"assertion":[{"value":"2025-08-22","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-17","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-08-17","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}