MCR-Tree: An Efficient Index for Multi-dimensional Core Search
Article No.: 153, Pages 1 - 25
Abstract
Core models are well-known cohesive subgraph models for graph analytics that have been extensively studied. These models, including (α, β)-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.
References
[1]
Akhlaque Ahmad, Lyuheng Yuan, Da Yan, Guimu Guo, Jieyang Chen, and Chengcui Zhang. 2023. Accelerating k-Core Decomposition by a GPU. In 39th IEEE International Conference on Data Engineering. 1818--1831.
[2]
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.
[3]
Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and Bishwamittra Ghosh. 2023. Neighborhood-based Hypergraph Core Decomposition. Proceedings of the VLDB Endowment, Vol. 16, 9 (2023), 2061--2074.
[4]
Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and Effective Community Search. Data Mining and Knowledge Discovery, Vol. 29 (2015), 1406--1433.
[5]
Norbert Beckmann and Bernhard Seeger. 2009. A Revised R*-tree in Comparison with Related Index Structures. In Proceedings of the 2009 ACM SIGMOD International Conference on Management of data. 799--812.
[6]
Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core Decomposition of Uncertain Graphs. In Proceedings of the 20th ACM SIGKDD International Conference on Knowledge discovery and data mining. 1316--1325.
[7]
Francesco Bonchi, Arijit Khan, and Lorenzo Severini. 2019. Distance-generalized Core Decomposition. In Proceedings of the 2019 International Conference on Management of Data. 1006--1023.
[8]
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.
[9]
James Cheng, Yiping Ke, Shumo Chu, and M Tamer Özsu. 2011. Efficient Core Decomposition in Massive Networks. In 2011 IEEE 27th International Conference on Data Engineering. 51--62.
[10]
Deming Chu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2022. Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search. In 38th IEEE International Conference on Data Engineering. 1138--1151.
[11]
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2022. Introduction to Algorithms. MIT press.
[12]
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.
[13]
Naga Shailaja Dasari, Ranjan Desh, and Mohammad Zubair. 2014. ParK: An Efficient Algorithm for k-core Decomposition on Multicore Processors. In 2014 IEEE International Conference on Big Data. 9--16.
[14]
Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017. Efficient Fault-tolerant Group Recommendation Using Alpha-beta-core. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 2047--2050.
[15]
Hossein Esfandiari, Silvio Lattanzi, and Vahab Mirrokni. 2018. Parallel and Streaming Algorithms for k-Core Decomposition. In International Conference on Machine Learning. 1397--1406.
[16]
Yixiang Fang, Zhongran Wang, Reynold Cheng, Hongzhi Wang, and Jiafeng Hu. 2018. Effective and Efficient Community Search over Large Directed Graphs. IEEE Transactions on Knowledge and Data Engineering, Vol. 31, 11 (2018), 2093--2107.
[17]
Edoardo Galimberti, Francesco Bonchi, and Francesco Gullo. 2017. Core Decomposition and Densest Subgraph in Multilayer Networks. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management. 1807--1816.
[18]
Edoardo Galimberti, Francesco Bonchi, Francesco Gullo, and Tommaso Lanciano. 2020. Core Decomposition in Multilayer Networks: Theory, Algorithms, and Applications. ACM Transactions on Knowledge Discovery from Data, Vol. 14, 1 (2020), 1--40.
[19]
Sen Gao, Rong-Hua Li, Hongchao Qin, Hongzhi Chen, Ye Yuan, and Guoren Wang. 2022. Colorful h-star Core Decomposition. In 38th IEEE International Conference on Data Engineering. 2588--2601.
[20]
Christos Giatsidis, Bogdan Cautis, Silviu Maniu, Dimitrios M. Thilikos, and Michalis Vazirgiannis. 2014. Quantifying Trust Dynamics in Signed Graphs, the S-Cores Approach. In Proceedings of the 2014 SIAM International Conference on Data Mining. 668--676.
[21]
Christos Giatsidis, Dimitrios M Thilikos, and Michalis Vazirgiannis. 2013. D-cores: Measuring Collaboration of Directed Graphs Based on Degeneracy. Knowledge and Information Systems, Vol. 35, 2 (2013), 311--343.
[22]
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.
[23]
Antonin Guttman. 1984. R-trees: A Dynamic Index Structure for Spatial Searching. In Proceedings of the 1984 ACM SIGMOD International Conference on Management of Data. 47--57.
[24]
Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2017. Community search over big graphs: Models, algorithms, and opportunities. In Proceedings of the 33rd IEEE International Conference on Data Engineering (ICDE). 1451--1454.
[25]
Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2019. Community Search over Big Graphs. Morgan & Claypool Publishers.
[26]
Xun Jian, Yue Wang, and Lei Chen. 2020. Effective and Efficient Relational Community Detection and Search in Large Dynamic Heterogeneous Information Networks. Proceedings of the VLDB Endowment, Vol. 13, 10 (2020), 1723--1736.
[27]
Xuankun Liao, Qing Liu, Jiaxin Jiang, Xin Huang, Jianliang Xu, and Byron Choi. 2022. Distributed D-core Decomposition over Large Directed Graphs. Proceedings of the VLDB Endowment, Vol. 15, 8 (2022), 1546--1558.
[28]
Zhe Lin, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Zhihong Tian. 2021. Hierarchical Core Maintenance on Large Dynamic Graphs. Proceedings of the VLDB Endowment, Vol. 14, 5 (2021), 757--770.
[29]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2019. Efficient (α, β)-core Computation: An Index-based Approach. In The World Wide Web Conference. 1130--1141.
[30]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2020. Efficient (α, β)-core Computation in Bipartite Graphs. The VLDB Journal, Vol. 29, 5 (2020), 1075--1099.
[31]
Qing Liu, Xuankun Liao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2023. Distributed ((α), (β))-Core Decomposition over Bipartite Graphs. In 39th IEEE International Conference on Data Engineering. 909--921.
[32]
Qing Liu, Xuliang Zhu, Xin Huang, and Jianliang Xu. 2021. Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs. Proceedings of the VLDB Endowment, Vol. 14, 9 (2021), 1531--1543.
[33]
Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016. The H-index of a Network Node and Its Relation to Degree and Coreness. Nature Communications, Vol. 7, 1 (2016), 10168.
[34]
Zhao Lu, Yuanyuan Zhu, Ming Zhong, and Jeffrey Xu Yu. 2022. On Time-optimal (k, p)-core Community Search in Dynamic Graphs. In 2022 IEEE 38th International Conference on Data Engineering. 1396--1407.
[35]
Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020. The Core Decomposition of Networks: Theory, Algorithms and Applications. The VLDB Journal, Vol. 29 (2020), 61--92.
[36]
Aritra Mandal and Mohammad Al Hasan. 2017. A Distributed k-core Decomposition Algorithm on Spark. In 2017 IEEE International Conference on Big Data. 976--981.
[37]
David W Matula and Leland L Beck. 1983. Smallest-last Ordering and Clustering and Graph Coloring Algorithms. J. ACM, Vol. 30, 3 (1983), 417--427.
[38]
Amir Mehrafsa, Sean Chester, and Alex Thomo. 2020. Vectorising k-Core Decomposition for GPU Acceleration. In 32nd International Conference on Scientific and Statistical Database Management. 24:1--24:4.
[39]
Alberto Montresor, Francesco De Pellegrini, and Daniele Miorandi. 2013. Distributed k-Core Decomposition. IEEE Trans. Parallel Distributed Syst., Vol. 24, 2 (2013), 288--300.
[40]
Michael P O'Brien and Blair D Sullivan. 2014. Locally Estimating Core Numbers. In 2014 IEEE International Conference on Data Mining. 460--469.
[41]
You Peng, Ying Zhang, Wenjie Zhang, Xuemin Lin, and Lu Qin. 2018. Efficient Probabilistic k-core Computation on Uncertain Graphs. In 2018 IEEE 34th International Conference on Data Engineering. 1192--1203.
[42]
Ahmet Erdem Sariyüce, C Seshadhri, and Ali Pinar. 2018. Local Algorithms for Hierarchical Dense Subgraph Discovery. Proceedings of the VLDB Endowment, Vol. 12, 1 (2018), 43--56.
[43]
Mauro Sozio and Aristides Gionis. 2010. The Community-search Problem and How to Plan a Successful Cocktail Party. In Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 939--948.
[44]
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.
[45]
Dong Wen, Lu Qin, Ying Zhang, Xuemin Lin, and Jeffrey Xu Yu. 2016. I/O Efficient Core Graph Decomposition at Web Scale. In 2016 IEEE 32nd International Conference on Data Engineering. 133--144.
[46]
Yikai Zhang, Jeffrey Xu Yu, Ying Zhang, and Lu Qin. 2017. A Fast Order-based Approach for Core Maintenance. In 2017 IEEE 33rd International Conference on Data Engineering. 337--348.
Index Terms
- MCR-Tree: An Efficient Index for Multi-dimensional Core Search
Recommendations
Evaluating multi-core and many-core architectures through accelerating the three-dimensional Lax-Wendroff correction stencil
Wave propagation forward modeling is a widely used computational method in oil and gas exploration. The iterative stencil loops in such problems have broad applications in scientific computing. However, executing such loops can be highly time-consuming, ...
Parallel Monte Carlo Tree Search from Multi-core to Many-core Processors
TRUSTCOM-BIGDATASE-ISPA '15: Proceedings of the 2015 IEEE Trustcom/BigDataSE/ISPA - Volume 03In recent years there has been much interest in the MCTS algorithm, a new, adaptive, randomized optimization algorithm. In fields as diverse as Artificial Intelligence, Operations Research, and High Energy Physics, research has established that MCTS can ...
The Inverted Multi-Index
A new data structure for efficient similarity search in very large datasets of high-dimensional vectors is introduced. This structure called the inverted multi-index generalizes the inverted index idea by replacing the standard quantization within ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
1953 pages
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 30 May 2024
Published in PACMMOD Volume 2, Issue 3
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 316Total Downloads
- Downloads (Last 12 months)316
- Downloads (Last 6 weeks)44
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in