University of Cambridge > Talks.cam > Computer Laboratory talks > Counting Subgraphs in Data Streams

Counting Subgraphs in Data Streams

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Dr Thomas Sauerwald.

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.

This talk is part of the Computer Laboratory talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2021 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity