Visualization Projects

Many of the projects I work on have strong visualization components and one of my main research interests is the interactive presentation of large amounts of information.

Large graphs are difficult to visualize. The standard node-link representation scales to only a few thousand nodes and edges on standard displays before becoming unreadable. Additionaly, the layout algorithms tend to be expensive while failing to improve on human generated layouts.

In this research, we explored matrix visualizations as an alternative to node-link representations. Matrix visualizations label the axes of the plot with the graph's nodes and display a dot in the plot area for each edge. Matrix visualizations scale to very large graphs on commoditiy hardware, making them attractive for large graph visualization. However, matrix visualizations also suffer from a layout challenge: the order of the vertices on the axes determines what features are visible in the plot area. A good ordering can reveal complex structure whereas a poor ordering creates a plot that is indistinguishable from noise.

To explore different ordering algorithms, we conducted a comprehensive survey of algorithms designed for re-ordering sparse matrices. Good memory layouts for sparse matrices are visually similar to good matrix visualization layouts. The results of our studies are reported in two papers in the Asia-Pacific Symposium on Information Visualization:

• A Comparison of Vertex Ordering Algorithms for Large Graph Visualization
  Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. To appear in APVIS2007.
  
  
• Interpreting Large Visual Similarity Matrices
  Christopher Mueller, Benjamin Martin, and Andrew Lumsdaine. To appear in APVIS2007.
  
  
• Matrix visualizations generated for the studies.

The most important meta-result of this work is the continued accumlation of evidence suggesting that algorithm selection for graph interpretation is heavily dependent on the underlying graph itself. What works well for a bipartite graph may not work at all on a small-world graph. This, of course, opens up the possibility that graph analysis may never be solved computationally and will always require human experts. In that case, the research community may need to shift focus towards exploring techniques for human interaction with very large graphs rather than automated information extraction.

Display wall: check.
Parallel graph library: check.
Distributed rednering system: check.

Too much free time? Well, not really, but why not see what it takes to parallelize a force-directed layout algorithm for interactive use on a display wall?

• Distributed Force-Directed Graph Layout and Visualization
  Christopher Mueller, Douglas Gregor, and Andrew Lumsdaine.
  In Eurographics Symposium on Parallel Graphics and Visualization (EGPVG'06), May 2006.

Over Thanksgiving break in 2004, we built a prototype display wall we built using 23" Apple displays. It was driven by a 5-node Linux cluster running Chromium. We hope to rebuild it using 30" displays soon. :) We also wrote some tools for displaying images on the display wall. Contact me for copies (license is not worked out yet).

• Actual Display Wall Prototype (html)
• Virtual Tiled wall 'prototypes' (html)
• Paner - an application for preparing images for display on tiled display walls. It takes a singly image and generates tiles for each display, scaling and letterboxing as needed. It also includes support for hiding parts of the image behind the gaps created by the display panes— which gives the effect of looking through a window. (contact me for a copy)
• wsetbg - an application for displaying background images on a tiled display wall (contact me for a copy)

See my Bioinformatics page for details on HPC Dotplot project.