{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T16:39:43Z","timestamp":1788626383510,"version":"build-2803163510"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Core models are well-known cohesive subgraph models for graph analytics that have been extensively studied. These models, including (\u03b1, \u03b2)-core, (k, l)-core, and k -core, have multiple parameters, which are referred to as multi-dimensional cores. The goal of core search is to retrieve subgraphs from a graph that satisfy the semantics of a given core model. In the literature, various indexes have been proposed to accelerate core search for different core models. However, existing indexes suffer from several limitations, such as significant redundancy, lack of scalability with respect to the number of parameters, limited generality, and inadequate consideration of index maintenance. To address these limitations, in this paper, we thoroughly investigate the problem of multi-dimensional core search. In particular, we propose a novel index called MCR-Tree, which can be applied to different core models. The MCR-Tree projects all vertices into a multi-dimensional space by leveraging the skyline corenesses, which are indexed by an R-tree. Furthermore, the MCR-Tree integrates the connectivity information of subgraphs into the nodes of the R-tree to facilitate multi-dimensional core search. Subsequently, an efficient branch-and-bound algorithm is designed to perform multi-dimensional core search by traversing the MCR-Tree. Additionally, we discuss how to maintain the MCR-Tree for graph updates. Extensive experiments demonstrate that the MCR-Tree is up to two orders of magnitude smaller than existing indexes and the MCR-Tree-based core search method is up to an order of magnitude faster than existing algorithms.<\/jats:p>","DOI":"10.1145\/3654956","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":5,"title":["MCR-Tree: An Efficient Index for Multi-dimensional Core Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-4718-3352","authenticated-orcid":false,"given":"Chengyang","family":"Luo","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4555-6232","authenticated-orcid":false,"given":"Yifan","family":"Zhu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-2775-4255","authenticated-orcid":false,"given":"Qing","family":"Liu","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3816-8450","authenticated-orcid":false,"given":"Yunjun","family":"Gao","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5685-7017","authenticated-orcid":false,"given":"Lu","family":"Chen","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9404-5848","authenticated-orcid":false,"given":"Jianliang","family":"Xu","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00142"},{"key":"e_1_2_1_2_1","volume-title":"Visualisation and Analysis of the Internet Movie Database. In 2007 6th International Asia-Pacific Symposium on Visualization. 17--24","author":"Ahmed Adel","year":"2007","unstructured":"Adel Ahmed, Vladimir Batagelj, Xiaoyan Fu, Seok-Hee Hong, Damian Merrick, and Andrej Mrvar. 2007. Visualisation and Analysis of the Internet Movie Database. In 2007 6th International Asia-Pacific Symposium on Visualization. 17--24."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3598581.3598582"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0422-1"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559929"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 3544--3550","author":"Chen Yankai","year":"2021","unstructured":"Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. 2021. Efficient Community Search over Large Directed Graphs: An Augmented Index-based Approach. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence. 3544--3550."},{"key":"e_1_2_1_9_1","volume-title":"Efficient Core Decomposition in Massive Networks. In 2011 IEEE 27th International Conference on Data Engineering. 51--62","author":"Cheng James","year":"2011","unstructured":"James Cheng, Yiping Ke, Shumo Chu, and M Tamer \u00d6zsu. 2011. Efficient Core Decomposition in Massive Networks. In 2011 IEEE 27th International Conference on Data Engineering. 51--62."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00090"},{"key":"e_1_2_1_11_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to Algorithms. MIT press."},{"key":"e_1_2_1_12_1","first-page":"196","article-title":"Core Decomposition on Uncertain Graphs Revisited","volume":"35","author":"Dai Qiangqiang","year":"2023","unstructured":"Qiangqiang Dai, Rong-Hua Li, Guoren Wang, Rui Mao, Zhiwei Zhang, and Ye Yuan. 2023. Core Decomposition on Uncertain Graphs Revisited. IEEE Trans. Knowl. Data Eng. , Vol. 35, 1 (2023), 196--210.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2014.7004366"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133130"},{"key":"e_1_2_1_15_1","volume-title":"International Conference on Machine Learning. 1397--1406","author":"Esfandiari Hossein","year":"2018","unstructured":"Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. 2018. Parallel and Streaming Algorithms for k-Core Decomposition. In International Conference on Machine Learning. 1397--1406."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00239"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.77"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0539-0"},{"key":"e_1_2_1_22_1","volume-title":"Nimblecore: A Space-efficient External Memory Algorithm for Estimating Core Numbers. In 2016 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining. 207--214","author":"Govindan Priya","year":"2016","unstructured":"Priya Govindan, Sucheta Soundarajan, Tina Eliassi-Rad, and Christos Faloutsos. 2016. Nimblecore: A Space-efficient External Memory Algorithm for Estimating Core Numbers. In 2016 IEEE\/ACM International Conference on Advances in Social Networks Analysis and Mining. 207--214."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.211"},{"key":"e_1_2_1_25_1","volume-title":"Laks VS Lakshmanan, and Jianliang Xu","author":"Huang Xin","year":"2019","unstructured":"Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2019. Community Search over Big Graphs. Morgan & Claypool Publishers."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401969"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3529337.3529340"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_31_1","volume-title":"39th IEEE International Conference on Data Engineering. 909--921","author":"Liu Qing","year":"2023","unstructured":"Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2023. Distributed ((\u03b1), (\u03b2))-Core Decomposition over Bipartite Graphs. In 39th IEEE International Conference on Data Engineering. 909--921."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3461535.3461542"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10168"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00109"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258018"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400903.3400931"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_40_1","volume-title":"Locally Estimating Core Numbers. In 2014 IEEE International Conference on Data Mining. 460--469","author":"O'Brien Michael P","year":"2014","unstructured":"Michael P O'Brien and Blair D Sullivan. 2014. Locally Estimating Core Numbers. In 2014 IEEE International Conference on Data Mining. 460--469."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00110"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_44_1","volume-title":"Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. In 2022 IEEE 38th International Conference on Data Engineering. 2291--2305","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Shunyang Li. 2022. Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. In 2022 IEEE 38th International Conference on Data Engineering. 2291--2305."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:40:30Z","timestamp":1755787230000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":46,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654956"],"URL":"https:\/\/doi.org\/10.1145\/3654956","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}