{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T17:18:31Z","timestamp":1763572711227,"version":"3.41.0"},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"State Key Laboratory of Communication Content Cognition Funded Project","award":["A32003"],"award-info":[{"award-number":["A32003"]}]},{"DOI":"10.13039\/501100012166","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2019YFB2101903"],"award-info":[{"award-number":["2019YFB2101903"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U22A2025,61972275"],"award-info":[{"award-number":["U22A2025,61972275"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>Reachability query is a fundamental problem and has been well studied on static graphs. However, in the real world, the graphs are not static but always evolving over time. In this paper, we study the problem of historical reachability query on evolving graphs. We propose a novel index, named HR-Index, which integrates complete and correct historical reachability information of the evolving graph. A historical reachability query on an evolving graph can be converted into a static reachability query on its HR-Index and thus query efficiency can be improved significantly. We also propose two optimization techniques to reduce the size of HR-Index effectively. We confirm the effectiveness and efficiency of our method through conducting extensive experiments on real-life datasets. Experimental results show both vertex and edge size of HR-Index are far smaller than that of the evolving graphs and our method has at least an order of magnitude improvement in time and space efficiency compared to the state-of-the-art method.<\/jats:p>","DOI":"10.1145\/3589272","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-25","source":"Crossref","is-referenced-by-count":1,"title":["HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0824-2931","authenticated-orcid":false,"given":"Yajun","family":"Yang","sequence":"first","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University; State Key Laboratory of Communication Content Cognition, People's Daily Online, Tianjin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6732-6417","authenticated-orcid":false,"given":"Hanxiao","family":"Li","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-3604-2821","authenticated-orcid":false,"given":"Xiangju","family":"Zhu","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2962-1604","authenticated-orcid":false,"given":"Junhu","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Information and Communication Technology, Griffith University, Gold Coast, Australia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9651-0651","authenticated-orcid":false,"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"College of Intelligence and Computing, Tianjin University, Tianjin, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2000-6683","authenticated-orcid":false,"given":"Hong","family":"Gao","sequence":"additional","affiliation":[{"name":"School of Computer Science and Technology, Zhejiang Normal University, Jinhua, China"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Proceedings of the 31st International Conference on Very Large Data Bases","author":"Chen Li","year":"2005","unstructured":"Li Chen, Amarnath Gupta, and M. Erdem Kurul. 2005. Stack-based Algorithms for Pattern Matching on DAGs. In Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005, Klemens B\u00f6 hm, Christian S. Jensen, Laura M. Haas, Martin L. Kersten, Per-\u00c5ke Larson, and Beng Chin Ooi (Eds.). ACM, 493--504. http:\/\/www.vldb.org\/archives\/website\/2005\/program\/paper\/wed\/p493-chen.pdf"},{"doi-asserted-by":"publisher","key":"e_1_2_2_2_1","DOI":"10.14778\/3467861.3467873"},{"doi-asserted-by":"publisher","key":"e_1_2_2_3_1","DOI":"10.1109\/ICDE.2008.4497498"},{"doi-asserted-by":"publisher","key":"e_1_2_2_4_1","DOI":"10.1145\/2463676.2465286"},{"doi-asserted-by":"publisher","key":"e_1_2_2_5_1","DOI":"10.5555\/545381.545503"},{"doi-asserted-by":"publisher","key":"e_1_2_2_6_1","DOI":"10.1016\/j.eswa.2021.114962"},{"doi-asserted-by":"publisher","key":"e_1_2_2_7_1","DOI":"10.1145\/99935.99944"},{"doi-asserted-by":"publisher","key":"e_1_2_2_8_1","DOI":"10.14778\/2556549.2556578"},{"doi-asserted-by":"publisher","key":"e_1_2_2_9_1","DOI":"10.1145\/1376616.1376677"},{"doi-asserted-by":"publisher","key":"e_1_2_2_10_1","DOI":"10.1109\/ICDE.2013.6544892"},{"key":"e_1_2_2_11_1","volume-title":"On Graph Deltas for Historical Queries. CoRR","author":"Koloniari Georgia","year":"2013","unstructured":"Georgia Koloniari, Dimitris Souravlias, and Evaggelia Pitoura. 2013. On Graph Deltas for Historical Queries. CoRR, Vol. abs\/1302.5549 (2013). arxiv: 1302.5549 http:\/\/arxiv.org\/abs\/1302.5549"},{"key":"e_1_2_2_12_1","volume-title":"Proceedings of the First International Workshop on Big Dynamic Distributed Data, Riva del Garda","volume":"48","author":"Labouseur Alan G.","year":"2013","unstructured":"Alan G. Labouseur, Paul W. Olsen, and Jeong-Hyon Hwang. 2013. Scalable and Robust Management of Dynamic Graph Data. In Proceedings of the First International Workshop on Big Dynamic Distributed Data, Riva del Garda, Italy, August 30, 2013 (CEUR Workshop Proceedings, Vol. 1018), Graham Cormode, Ke Yi, Antonios Deligiannakis, and Minos N. Garofalakis (Eds.). CEUR-WS.org, 43--48. http:\/\/ceur-ws.org\/Vol-1018\/paper7.pdf"},{"doi-asserted-by":"publisher","key":"e_1_2_2_13_1","DOI":"10.14778\/3402707.3402713"},{"doi-asserted-by":"publisher","key":"e_1_2_2_14_1","DOI":"10.1137\/13093618X"},{"doi-asserted-by":"publisher","key":"e_1_2_2_15_1","DOI":"10.5441\/002"},{"doi-asserted-by":"publisher","key":"e_1_2_2_16_1","DOI":"10.1109\/ICDE.2019.00049"},{"doi-asserted-by":"publisher","key":"e_1_2_2_17_1","DOI":"10.1109\/ICDE.2013.6544893"},{"doi-asserted-by":"publisher","key":"e_1_2_2_18_1","DOI":"10.1145\/1247480.1247573"},{"doi-asserted-by":"publisher","key":"e_1_2_2_19_1","DOI":"10.1109\/ICDE.2006.53"},{"doi-asserted-by":"publisher","key":"e_1_2_2_20_1","DOI":"10.1007\/s00778-017-0468--3"},{"doi-asserted-by":"publisher","key":"e_1_2_2_21_1","DOI":"10.1109\/ICDE48307.2020.00104"},{"doi-asserted-by":"publisher","key":"e_1_2_2_22_1","DOI":"10.1109\/ICDE.2016.7498236"},{"doi-asserted-by":"publisher","key":"e_1_2_2_23_1","DOI":"10.1007\/s00778-011-0256--4"},{"key":"e_1_2_2_24_1","volume-title":"Zaki","author":"Yildirim Hilmi","year":"2013","unstructured":"Hilmi Yildirim, Vineet Chaoji, and Mohammed J. Zaki. 2013. DAGGER: A Scalable Index for Reachability Queries in Large Dynamic Graphs. CoRR, Vol. abs\/1301.0977 (2013). arxiv: 1301.0977 http:\/\/arxiv.org\/abs\/1301.0977"},{"doi-asserted-by":"publisher","key":"e_1_2_2_25_1","DOI":"10.1007\/s00778-019-00572-x"},{"doi-asserted-by":"publisher","key":"e_1_2_2_26_1","DOI":"10.1109\/ICDE.2018.00153"},{"doi-asserted-by":"publisher","key":"e_1_2_2_27_1","DOI":"10.1145\/2588555.2612181"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589272","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589272","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:48:54Z","timestamp":1750182534000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589272"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589272"],"URL":"https:\/\/doi.org\/10.1145\/3589272","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}