时间：11月2日（周六）下午2:30

地点：信息科学与工程学院220（原106）

个人介绍：

Lei Zou received his BS degree and Ph.D. degree in Computer Science at Huazhong University of Science and Technology (HUST) in 2003 and 2009, respectively. He received a CCF (China Computer Federation) Doctoral Dissertation Nomination Award in 2009, won Second Class Prize of CCF Natural Science Award in 2014 and Second Class Prize of Natural Science of the Ministry of Education, China in 2017. Since September 2009, he joined Institute of Computer Science and Technology (ICST) of Peking University (PKU) as a faculty member. He has been a professor in PKU since August 2017.Before joining PKU, Lei Zou visited Hong Kong University of Science and Technology in 2007 and University of Waterloo in 2008 as a visiting scholar. His recent research interests include graph databases, knowledge graph, particularly in graph-based RDF data management. He has published more than 40 papers, including more than 30 papers published in reputed journals and major international conferences, such as SIGMOD, VLDB, ICDE, AAAI, TODS, TKDE, VLDB Journal.

报告摘要:

In this talk, I focus on accelerating a widely employed computing pattern—set intersection, to boost a group of relevant graph algorithms. Graph’s adjacency-lists can be naturally considered as node sets, thus set intersection is a primitive operation in many graph algorithms. We propose QFilter, a set intersection algorithm using SIMD instructions. QFilter adopts a merge-based framework and compares two blocks of elements iteratively by SIMD instructions. The key insight for our improvement is that we quickly filter most of unnecessary comparisons in one byte-checking step.We also present a binary representation called BSR that represent sets in a compact layout. From the combination of QFilter and BSR, we achieve dataparallelism in two levels—inter-chunk and intra-chunk parallelism. Furthermore, we find that node ordering impacts the performance of intersection in graph algorithms by affecting the compactness of BSR. We formulate the graph reordering problem as an optimization of the compactness of BSR, and prove its strong NP-completeness. Thus we propose an approximate algorithm that can find a better ordering and improve the performance by 39% on average.