Abstract

The recent explosion in the number and scale of real-world structured graphs including the web, social and biological networks, and graph databases has created a pressing need to efficiently analyze the structures of massive graphs. While traditional algorithms store the whole graph and cannot even deal with graphs of medium size, a modern approach is to process the graph as a data stream where edges of the graph come sequentially. Streaming algorithms need to capture the graph structures in sub-linear space, and approximate certain quantities of the underlying graph. In this talk we discuss this line of research including our recent techniques for counting arbitrary subgraphs in the streaming setting.

Bio:

He Sun obtained his PhD from Fudan University in 2010, and was a PostDoc at the Max Planck Institute for Informatics in Saarbruecken from 2010-2012. Since this summer, He Sun is a leader of a research group on randomized algorithms within the Cluster of Excellence at Saarland University. He is also affiliated with the Max Planck Institute for Informatics as a senior researcher in the Department of Algorithms and Complexity. He Sun’s research area lies at the intersection between Algorithm Design and Complexity Theory. He has worked extensively in streaming algorithms, distributed algorithms and computational geometry.