Large-scale Graph Analysis: System, Algorithm and Optimization

This book introduces readers to a workload-aware methodology for large-scale graph algorithm optimization in graph-computing systems, and proposes several optimization techniques that can enable these systems to handle advanced graph algorithms efficiently. More concretely, it proposes a workload-aware cost model to guide the development of high-performance algorithms. On the basis of the cost model, the book subsequently presents a system-level optimization resulting in a partition-aware graph-computing engine, PAGE. In addition, it presents three efficient and scalable advanced graph algorithms the subgraph enumeration, cohesive subgraph detection, and graph extraction algorithms.

This book offers a valuable reference guide for junior researchers, covering the latest advances in large-scale graph analysis; and for senior researchers, sharing state-of-the-art solutions based on advanced graph algorithms. In addition, all readers will find a workload-aware methodology fordesigning efficient large-scale graph algorithms.

Shares techniques for optimizing large-scale graph algorithms in distributed settings Introduces three optimized graph analysis algorithms (i.e., subgraph enumeration, subgraph detection and graph extraction) for large graphs Presents a distributed graph-computing system that can intelligently utilize high-quality graph partitions to boost efficiency

Auteur

Yingxia Shao is a Research Associate Professor at the School of Computer Science, Beijing University of Posts and Telecommunications. His research interests include large-scale graph analysis, knowledge graph management and representation, and parallel computing. He obtained his PhD from Peking University in 2016, under the supervision of Prof. Bin Cui. He worked with Prof. Lei Chen as a visiting scholar at HKUST in 2013 and 2014. He has served in the Technical Program Committee of various international conferences including VLDB, KDD, AAAI, IJCAI, DASFAA, BigData, APWeb-WAIM and MDM. He is serving as a reviewer of international journals including VLDBJ, DAPD, WWWJ, DSE. He was selected for a Google PhD Fellowship (2014), MSRA Fellowship (2014), PhD National Scholarship of MOE China (2014), ACM SIGMOD China Doctoral Dissertation Award (2017). He is currently a member of the ACM, IEEE, CCF, and China Database technical committee.

Bin Cui is a Professor at the School of EECS and Director of the Institute of Network Computing and Information Systems, at Peking University. He obtained his B.Sc. from Xi'an Jiaotong University (Pilot Class) in 1996, and Ph.D. from National University of Singapore in 2004 respectively. From 2004 to 2006, he worked as a Research Fellow in Singapore-MIT Alliance. His research interests include database system architectures, query and index techniques, and big data management and mining. He has served in the Technical Program Committee of various international conferences including SIGMOD, VLDB, ICDE and KDD, and as Vice PC Chair of ICDE 2011, Demo Co-Chair of ICDE 2014, Area Chair of VLDB 2014, PC Co-Chair of APWeb 2015 and WAIM 2016. He is currently serving as a Trustee Board Member of VLDB Endowment, , is on the the Editorial Board of VLDB Journal, Distributed and Parallel Databases Journal, and Information Systems, and was formerly an associate editor of IEEE Transactions on Knowledge and Data Engineering (TKDE, 2009-2013). He was selected for a Microsoft Young Professorship award (MSRA 2008), CCF Young Scientist award (2009), Second Prize of Natural Science Award of MOE China (2014), and appointed a Cheung Kong distinguished Professor by the MOE in 2016. He is a senior member of the IEEE, member of the ACM and distinguished member of the CCF.

Lei Chen received the BS degree in computer science and engineering from Tianjin University, Tianjin, China, in 1994, the MA degree from Asian Institute of Technology, Bangkok, Thailand, in 1997, and the Ph.D. degree in computer science from the University of Waterloo, Canada, in 2005. He is currently a Full Professor at the Department of Computer Science and Engineering, Hong Kong University of Science and Technology. His research interests include crowdsourcing, social media analysis, probabilistic and uncertain databases, and privacy-preserved data publishing. The system developed by his team won the excellent demonstration award at the VLDB 2014. He was selected for the SIGMOD Test-of-Time Award in 2015. He is PC Track chairs for SIGMOD 2014, VLDB 2014, ICDE 2012, CIKM 2012, SIGMM 2011. He has served as PC members for SIGMOD, VLDB, ICDE, SIGMM, and WWW. Currently, he serves as PC co-chair for VLDB 2019, Editor-in-Chief of VLDB Journal and associate editor-in-chief of IEEE Transactions on Data and Knowledge Engineering. He is an IEEE fellow, a member of the VLDB endowment and an ACM Distinguished Scientist.

Contenu

1. Introduction.- 2. Graph Computing Systems for Large-Scale Graph Analysis.- 3. Partition-Aware Graph Computing System.- 4. Efficient Parallel Subgraph Enumeration.- 5. Efficient Parallel Graph Extraction.- 6. Efficient Parallel Cohesive Subgraph Detection.- 7. Conclusions.