Counting Subgraphs in Data Streams

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

• Dr H Sun, Cluster of Excellence, Saarland University
• Tuesday 29 October 2013, 14:30-15:30
• FW11, Computer Laboratory, William Gates Builiding.

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 Department of Computer Science and Technology talks and seminars series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Department of Computer Science and Technology talks and seminars
• FW11, Computer Laboratory, William Gates Builiding
• Interested Talks
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.