{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:15:36Z","timestamp":1779174936552,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"5","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:p>\n            The recently proposed historical\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -core query introduces a new paradigm of structure analysis for temporal graphs. However, the query processing based on the existing PHC-index, which preserves the distinct \"core time\" of each vertex, needs to traverse all vertices for each query, even though the results usually contain only a small subset of vertices. Inspired by the traditional\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -shell that ensures the optimal\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -core query processing, we propose a novel concept called \"core time shell\", which reveals the hierarchical structure of vertices with respect to their core time. Based on the core time shell, we design a time-space balanced Merged Core Time Shell index (MCTS-index). It is theoretically guaranteed that, the MCTS-index provides the approximately optimal query performance, and has the approximately same space complexity as the PHC-index. Moreover, we leverage the MCTS-index to efficiently address the brand-new \"when\" historical\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -core queries orthogonal to the current \"what\" historical\n            <jats:italic toggle=\"yes\">k<\/jats:italic>\n            -core queries. Our experimental results on ten real-world temporal graphs demonstrate both the superior efficiency of processing \"what\" queries and the effectiveness of processing versatile \"when\" queries for the MCTS-index.\n          <\/jats:p>","DOI":"10.14778\/3718057.3718063","type":"journal-article","created":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:11:49Z","timestamp":1756318309000},"page":"1335-1347","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On More Efficiently and Versatilely Querying Historical\n            <i>k<\/i>\n            -Cores"],"prefix":"10.14778","volume":"18","author":[{"given":"Zhi","family":"Wang","sequence":"first","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ming","family":"Zhong","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuanyuan","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science, Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tieyun","family":"Qian","sequence":"additional","affiliation":[{"name":"Wuhan University, Wuhan, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mengchi","family":"Liu","sequence":"additional","affiliation":[{"name":"South China Normal University, Guangzhou, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,8,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.11.003"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641213"},{"key":"e_1_2_1_3_1","volume-title":"2020 IEEE 36th International Conference on Data Engineering (ICDE).","author":"Chu Deming","year":"2020","unstructured":"Deming Chu, Fan Zhang, Xuemin Lin, Wenjie Zhang, Ying Zhang, Yinglong Xia, and Chenyi Zhang. 2020. Finding the Best k in Core Decomposition: A Time and Space Optimal Solution. In 2020 IEEE 36th International Conference on Data Engineering (ICDE)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358704"},{"key":"e_1_2_1_5_1","volume-title":"Kairos: Efficient Temporal Graph Analytics on a Single Machine. arXiv preprint arXiv:2401.02563","author":"da Trindade Joana MF","year":"2024","unstructured":"Joana MF da Trindade, Julian Shun, Samuel Madden, and Nesime Tatbul. 2024. Kairos: Efficient Temporal Graph Analytics on a Single Machine. arXiv preprint arXiv:2401.02563 (2024)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2023.3276190"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3641204.3641214"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2850469.2850471"},{"key":"e_1_2_1_9_1","volume-title":"Historical Graph Management","author":"Khurana Udayan","unstructured":"Udayan Khurana and Amol Deshpande. 2019. Historical Graph Management. Springer."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1746"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23495-9_2"},{"key":"e_1_2_1_13_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aai7488"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512226"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00917-z"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3648160.3648163"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Naoki Masuda and Renaud Lambiotte. 2021. A Guide to Temporal Networks. World Scientific.","DOI":"10.1142\/q0268"},{"key":"e_1_2_1_20_1","volume-title":"Makse","author":"Pei Sen","year":"2014","unstructured":"Sen Pei, Lev Muchnik, Jr. Jos\u00e9 S. Andrade, Zhiming Zheng, and Hern\u00e1n A. Makse. 2014. Searching for superspreaders of information in real-world social media. Scientific Reports (2014)."},{"key":"e_1_2_1_21_1","volume-title":"Historical Graphs: Models, Storage, Processing. In European Business Intelligence and Big Data.","author":"Pitoura Evaggelia","year":"2017","unstructured":"Evaggelia Pitoura. 2017. Historical Graphs: Models, Storage, Processing. In European Business Intelligence and Big Data."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565845"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-25158-0_38"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10270-021-00950-6"},{"key":"e_1_2_1_25_1","volume-title":"Article 157","author":"Song Jingyi","year":"2024","unstructured":"Jingyi Song, Dong Wen, Lantian Xu, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2024. On Querying Historical Connectivity in Temporal Graphs. 2, 3, Article 157 (2024), 25 pages."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551834"},{"key":"e_1_2_1_27_1","volume-title":"Ziyu Guan, Jiajie Xu, and Chengfei Liu.","author":"Tang Yifu","year":"2023","unstructured":"Yifu Tang, Jianxin Li, Nur Al Hasan Haldar, Ziyu Guan, Jiajie Xu, and Chengfei Liu. 2023. Reliability-driven local community search in dynamic networks. IEEE Transactions on Knowledge and Data Engineering (2023)."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3410647"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363809"},{"key":"e_1_2_1_30_1","volume-title":"Proc. ACM Manag. Data 1, 2, Article 170","author":"Xie Haoxuan","year":"2023","unstructured":"Haoxuan Xie, Yixiang Fang, Yuyang Xia, Wensheng Luo, and Chenhao Ma. 2023. On Querying Connected Components in Large Temporal Graphs. Proc. ACM Manag. Data 1, 2, Article 170 (2023), 27 pages."},{"key":"e_1_2_1_31_1","volume-title":"Scalable time-range k-core query on temporal graphs. arXiv preprint arXiv:2301.03770","author":"Yang Junyong","year":"2023","unstructured":"Junyong Yang, Ming Zhong, Yuanyuan Zhu, Tieyun Qian, Mengchi Liu, and Jeffrey Xu Yu. 2023. Scalable time-range k-core query on temporal graphs. arXiv preprint arXiv:2301.03770 (2023)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681967"},{"key":"e_1_2_1_33_1","first-page":"2","volume-title":"Proceedings of the ACM on Management of Data 1","author":"Yang Yajun","year":"2023","unstructured":"Yajun Yang, Hanxiao Li, Xiangju Zhu, Junhu Wang, Xin Wang, and Hong Gao. 2023. HR-Index: An Effective Index Method for Historical Reachability Queries over Evolving Graphs. Proceedings of the ACM on Management of Data 1, 2 (2023)."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476260"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2022.103170"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36461-7_5"},{"key":"e_1_2_1_37_1","volume-title":"Yu","author":"Zhong Ming","year":"2024","unstructured":"Ming Zhong, Junyong Yang, Yuanyuan Zhu, Tieyun Qian, Mengchi Liu, and Jeffrey X. Yu. 2024. A Unified and Scalable Algorithm Framework of User-Defined Temporal (k, X)-Core Query. IEEE Transactions on Knowledge and Data Engineering (2024)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3718057.3718063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T18:12:27Z","timestamp":1756318347000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3718057.3718063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["10.14778\/3718057.3718063"],"URL":"https:\/\/doi.org\/10.14778\/3718057.3718063","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2025,1]]},"assertion":[{"value":"2025-08-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}