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 J., vol. 28, no. 2, 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 J., 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.', Proc. VLDB Endow., 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.
View/Download from: Publisher's site

Zhu, Y, Zhang, H, Qin, L & Cheng, H 2017, 'Efficient MapReduce algorithms for triangle listing in billion-scale graphs.', Distributed 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 1970, 'Efficient Local Clustering Coefficient Estimation in Massive Graphs.', DASFAA (2), Database Systems for Advanced Applications, Springer, China, pp. 371-386.
View/Download from: Publisher's site

Zhu, Y, Li, Y, Liu, J, Qin, L & Yu, JX 1970, 'GMAlign: A new network aligner for revealing large conserved functional components.', BIBM, IEEE International Conference on Bioinformatics and Biomedicine, IEEE Computer Society, 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 Trans. Knowl. Data Eng., vol. 28, no. 12, pp. 3203-3217.
View/Download from: Publisher's site

Huang, X, Cheng, H, Li, R-H, Qin, L & Yu, JX 2015, 'Top-K structural diversity search in large networks.', VLDB J., vol. 24, no. 3, 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 Trans. Knowl. Data Eng., vol. 27, no. 9, 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 J., vol. 24, no. 2, pp. 245-270.
View/Download from: Publisher's site

Chang, L, Lin, X, Qin, L, Yu, JX & Pei, J 1970, 'Efficiently Computing Top-K Shortest Path Join.', EDBT, 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 1970, 'Optimal Enumeration: Efficient Top-k Tree Matching.', Proc. VLDB Endow., 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 1970, 'Scalable Subgraph Enumeration in MapReduce.', Proc. VLDB Endow., 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 1970, 'Influential Community Search in Large Networks.', Proc. VLDB Endow., 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, R-H, Yu, JX, Qin, L, Mao, R & Jin, T 1970, 'On random walk based graph sampling.', ICDE, IEEE International Conference on Data Engineering, IEEE Computer Society, Seoul, South Korea, pp. 927-938.
View/Download from: Publisher's site

Qin, L, Li, R-H, Chang, L & Zhang, C 1970, 'Locally Densest Subgraph Discovery.', KDD, ACM International Conference on Knowledge Discovery and Data Mining, ACM, Sydney, Australia, pp. 965-974.
View/Download from: Publisher's site

Wen, D, Qin, L, Zhang, Y, Lin, X & Yu, JX 1970, 'I/O Efficient Core Graph Decomposition at Web Scale.', CoRR, pp. 133-144.
View/Download from: Publisher's site

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

Zhang, S, Qin, L, Zheng, Y & Cheng, H 1970, 'Effective and efficient: large-scale dynamic city express.', SIGSPATIAL/GIS, ACM International Conference on Advances in Geographic Information Systems, ACM, Seattle, Washington, pp. 48:1-48:1.
View/Download from: Publisher's site

Zhu, Y, Yu, JX & Qin, L 2014, 'Leveraging Graph Dimensions in Online Graph Search.', Proc. VLDB Endow., vol. 8, no. 1, pp. 85-96.
View/Download from: Publisher's site

Huang, X, Cheng, H, Qin, L, Tian, W & Yu, JX 1970, 'Querying k-truss community in large and dynamic graphs.', SIGMOD Conference, 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 1970, 'Scalable big graph processing in MapReduce.', SIGMOD Conference, 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 1970, 'Contract & Expand: I/O Efficient SCCs Computing.', ICDE, IEEE International Conference on Data Engineering, IEEE Computer Society, 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, Database systems, Graph, social and multimedia data, Information systems, technologies and services not elsewhere classified

Acknowledgement of Country

UTS acknowledges the Gadigal people of the Eora Nation, the Boorooberongal people of the Dharug Nation, the Bidiagal people and the Gamaygal people, upon whose ancestral lands our university stands. We would also like to pay respect to the Elders both past and present, acknowledging them as the traditional custodians of knowledge for these lands.