Colloquium Speaker

Speaker: James Abello
AT&T Shannon Laboratory
Topic:MASSIVE MULTI-DIGRAPHS
Date:Tuesday, October 30, 2001
Time:11:00 AM
Place:Gould-Simpson, Room 701


Refreshments will be served in the 7th-floor lobby of Gould-Simpson at 10:45 AM


ABSTRACT


A variety of massive data sets exhibit an underlying structure that can be modeled as dynamic weighted multi-digraphs. Their sizes range from tens of gigabytes to petabytes. The sheer volume of these graphs brings with it an interesting series of computational and visualization challenges.

We will discuss external memory algorithms for connectivity, minimum spanning trees and maximal matchings together with heuristics for quasiclique finding and diameter computations. From the visualization store we will describe an external memory hierarchy that allow us to use computer graphics techniques like dynamic visibility to provide navigation control. The main elements of our current C-Java Massive Graph Visualizer will be introduced and a summary of experimental results with graphs having on the order of 200 million vertexes will be presented. We will point out some mathematical problems that have surfaced along the way.