This talk gives an overview of the state of the art in solving
problems on massive graphs beyond the size of main memory and
highlights some of the most important challenges in the area.  Massive
graphs arise in an increasing number of application areas, including
geographic information systems, web modelling, and computational
biology.  For example, route planning applications represent road
networks as graphs and solve shortest-path-type problems on them,
search engines analyze the web graph to identify web communities, and
a number of sequence analysis tasks in genomics reduce to analyzing
graphs that capture the structure of the given sequence.  The main
source of problems with processing massive graphs is that the graph
exploration strategies at the heart of virtually all traditional graph
algorithms are inherently inefficient on large graphs.  The first part
of the talk focuses on alternate techniques to solve problems on
massive graphs and on methods to speed up graph exploration approaches
on a number of input types.  The second part discusses current
research directions and challenges.

About the speaker:
Norbert Zeh is an Associate Professor and Canada Research Chair at the
Faculty of Computer Science of Dalhousie University in Halifax, Nova
Scotia, Canada.  He received his PhD in 2002 from Carleton University
and joined Dalhousie University in 2003 after a short postdoc at Duke
University.