Skip to main content

Big Graph Processing in MapReduce

Funding: 2014: $131,740
2015: $131,740
2016: $131,740

Funding or Partner Organisation: Australian Research Council (ARC DECRA Scheme)

Start year: 2014

Summary: As a large branch of big data processing, big graph processing is becoming increasingly important in both industry and academia, due to the large expressive power of graphs to model complex relationships among entities in the real world. This project aims to find highly scalable solutions to process big graphs using MapReduce. MapReduce is a big data processing framework that is shown to be scalable to handle SQL-styled queries but is still open when it is used to process big graphs. Most of the problems studied in this project are fundamental graph problems that are not well studied in MapReduce. The successful completion of this project will enhance the big graph processing which is beneficial for both science and society.

Publications:

Wang, X, Qin, L, Lin, X, Zhang, Y & Chang, L 2019, 'Leveraging set relations in exact and dynamic set similarity join', VLDB Journal, vol. 28, pp. 267-292.
View/Download from: Publisher's site

Lai, L, Qin, L, Lin, X & Chang, L 2017, 'Scalable subgraph enumeration in MapReduce: a cost-oriented approach', VLDB Journal, vol. 26, no. 3, pp. 421-446.
View/Download from: Publisher's site

Wang, X, Qin, L, Lin, X, Zhang, Y & Chang, L 2017, 'Leveraging Set Relations in Exact Set Similarity Join', PROCEEDINGS OF THE VLDB ENDOWMENT, vol. 10, no. 9, pp. 925-936.
View/Download from: Publisher's site

Zhang, F, Zhang, Y, Qin, L, Zhang, W & Lin, X 2017, 'When Engagement Meets Similarity: Efficient (k, r)-Core Computation on Social Networks.', Proc. VLDB Endow., vol. 10, pp. 998-1009.

Zhu, Y, Zhang, H, Qin, L & Cheng, H 2017, 'Efficient MapReduce algorithms for triangle listing in billion-scale graphs', Distributed and Parallel Databases, vol. 35, no. 2, pp. 149-176.
View/Download from: Publisher's site

Zhang, H, Zhu, Y, Qin, L, Cheng, H & Yu, JX 2017, 'Efficient local clustering coefficient estimation in massive graphs', Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Database Systems for Advanced Applications, China, pp. 371-386.
View/Download from: Publisher's site

Zhu, Y, Li, Y, Liu, J, Qin, L & Yu, JX 2017, 'GMAlign: A new network aligner for revealing large conserved functional components', Proceedings - 2017 IEEE International Conference on Bioinformatics and Biomedicine, BIBM 2017, IEEE International Conference on Bioinformatics and Biomedicine, IEEE, Kansas City, MO, USA, pp. 120-127.
View/Download from: Publisher's site

Zhang, S, Qin, L, Zheng, Y & Cheng, H 2016, 'Effective and Efficient: Large-Scale Dynamic City Express', IEEE Transactions on Knowledge and Data Engineering, vol. 28, no. 12, pp. 3203-3217.
View/Download from: Publisher's site

Wen, D, Qin, L, Zhang, Y, Lin, X & Yu, JX 2016, 'I/O Efficient Core Graph Decomposition at Web Scale.', CoRR.

Huang, X, Cheng, H, Li, R-H, Qin, L & Yu, JX 2015, 'Top-K structural diversity search in large networks.', The VLDB Journal, vol. 24, pp. 319-343.
View/Download from: Publisher's site

Li, Z, Qin, L, Cheng, H, Zhang, X & Zhou, X 2015, 'TRIP: An Interactive Retrieving-Inferring Data Imputation Approach.', IEEE Transactions on Knowledge and Data Engineering, vol. 27, pp. 2550-2563.
View/Download from: Publisher's site

Zhang, Z, Yu, JX, Qin, L, Chang, L & Lin, X 2015, 'I/O efficient: computing SCCs in massive graphs', VLDB Journal, vol. 24, no. 2, pp. 245-270.
View/Download from: Publisher's site

Chang, L, Lin, X, Qin, L, Yu, JX & Pei, J 2015, 'Efficiently Computing Top-K Shortest Path Join', Proceedings of the 18th International Conference on Extending Database Technology, EDBT 2015, Brussels, Belgium, March 23-27, 2015., Extending Database Technology, OpenProceedings.org, Belgium, pp. 133-144.
View/Download from: Publisher's site

Chang, L, Lin, X, Zhang, W, Yu, JX, Zhang, Y & Qin, L 2015, 'Optimal Enumeration: Efficient Top-k Tree Matching', Proceedings of the VLDB Endowment, International Conference on Very Large Databases, VLDB Endowment, Kahola Coast, Hawaii, pp. 533-544.
View/Download from: Publisher's site

Lai, L, Qin, L, Lin, X & Chang, L 2015, 'Scalable Subgraph Enumeration in MapReduce.', Proceedings of the VLDB Endowment, International Conference on Very Large Databases, VLDB Endowment, Kohala Coast, Hawaii, pp. 974-985.
View/Download from: Publisher's site

Li, R-H, Qin, L, Yu, JX & Mao, R 2015, 'Influential Community Search in Large Networks', Proceedings of the VLDB Endowment, International Conference on Very Large Databases, Proceedings of the Vldb Endowment International Conference on Very Large Data Bases, Kohala Coast, Hawaii, pp. 509-520.
View/Download from: Publisher's site

Li, RH, Yu, JX, Qin, L, Mao, R & Jin, T 2015, 'On random walk based graph sampling', Proceedings - International Conference on Data Engineering, IEEE International Conference on Data Engineering, IEEE, Seoul, South Korea, pp. 927-938.
View/Download from: Publisher's site

Qin, L, Li, RH, Chang, L & Zhang, C 2015, 'Locally densest subgraph discovery', Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM International Conference on Knowledge Discovery and Data Mining, ACM, Sydney, Australia, pp. 965-974.
View/Download from: Publisher's site

Yuan, L, Qin, L, Lin, X, Chang, L & Zhang, W 2015, 'Diversified top-k clique search', Proceedings - International Conference on Data Engineering, IEEE International Conference on Data Engineering, IEEE, South Korea, pp. 387-398.
View/Download from: Publisher's site

Zhang, S, Qin, L, Zheng, Y & Cheng, H 2015, 'Effective and efficient: Large-scale dynamic city express', Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, ACM International Conference on Advances in Geographic Information Systems, ACM, Seattle, Washington.
View/Download from: Publisher's site

Zhu, Y, Yu, JX & Qin, L 2014, 'Leveraging graph dimensions in online graph search', Proceedings of the VLDB Endowment, vol. 8, no. 1, pp. 85-96.
View/Download from: Publisher's site

Huang, X, Cheng, H, Qin, L, Tian, W & Yu, JX 2014, 'Querying k-truss community in large and dynamic graphs', International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, ACM Special Interest Group on Management of Data Conference, ACM, Utah, USA, pp. 1311-1322.
View/Download from: Publisher's site

Qin, L, Yu, JX, Chang, L, Cheng, H, Zhang, C & Lin, X 2014, 'Scalable big graph processing in MapReduce', International Conference on Management of Data, SIGMOD 2014, Snowbird, UT, USA, June 22-27, 2014, ACM Special Interest Group on Management of Data Conference, ACM, Utah, USA, pp. 827-838.
View/Download from: Publisher's site

Zhang, Z, Qin, L & Yu, JX 2014, 'Contract & Expand: I/O Efficient SCCs Computing', IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, IEEE International Conference on Data Engineering, IEEE, Chicago, IL, pp. 208-219.
View/Download from: Publisher's site

Keywords: Graph Processing,MapReduce,Database Management

FOR Codes: Database Management, Information Processing Services (incl. Data Entry and Capture), Pattern Recognition and Data Mining, Expanding Knowledge in the Information and Computing Sciences, Electronic Information Storage and Retrieval Services