Sample Projects


MASSIVE DATA SETS


Semi_external Algorithms Semi_External Depth First Search on Directed Graphs - with Jop F. Sibeyn and Ulrich Meyer.

Computing the strong components of a directed graph is an essential operation for a basic structural analysis of it. This problem can be solved by twice running a depth-first search (DFS). In an external setting, in which all data can no longer be stored in the main memory, the DFS problem is unsolved so far. Assuming that node-related data can be stored internally, semi-external computing does not make the problem substantially easier. Considering the definite need to analyze very large graphs, we have developed a set of heuristics which together allow the performance of semi-external DFS for directed graphs in practice. The heuristics have been applied to graphs with very different graph properties, including "web graphs" as described in the most recent literature and some large call graphs from ATT. Depending on the graph structure, the program is between 10 and 200 times faster than the best alternative, a factor that will further increase with future technological developments.

PDF "Heuristics for Semi_External Depth First Search on Directed Graphs", Proceedings of the ACM Symposium on Parallel Algorithms and Architectures, SPAA'02, pp. 282-292, 2002.

A Functional Approach to External Graph Algorithms - with A. Buschbaum and J. Westbrook.

We present a new approach for designing external graph algorithms and use it to design simple external algorithms for computing connected components, minimum spanning trees, bottleneck minimum spanning trees, and maximal matchings in undirected graphs and multi-graphs. Our I/O bounds compete with those of previous approaches. Unlike previous approaches, ours is purely functional---without side effects---and is thus amenable to standard checkpointing and programming language optimization

PDF "A Functional Approach to External Graph Algorithms ", Algorithmica (2002) 32: 437-458.
Quasi-Clique - with M. Resende and S. Sudarsky.

We present an approach for clique and quasi-clique computations in very large multi-digraphs. We discuss graph decomposition schemes used to break up the problem into several pieces of manageable dimensions. A semiexternal greedy randomized adaptive search procedure (GRASP) for finding approximate solutions to the maximum clique problem and maximum quasiclique problem in very large sparse graphs is presented.

PDF "Massive Quasi-Cliques Detection ", in LATIN , LNCS 2286, pp. 598-612, Springer Verlag, 2002.

VISUALIZATION AND DISTRIBUTED COMPUTING


Graph View GraphView - with F. van Ham and N. Krishnan.

We describe ASK-GraphView, a node-link-based graph visualization system that allows clustering and interactive navigation of large graphs, ranging in size up to 16 million edges. The system uses a scalable architecture and a series of increasingly sophisticated clustering algorithms to construct a hierarchy on an arbitrary, weighted undirected input graph. By lowering the interactivity requirements we can scale to substantially bigger graphs. The user is allowed to navigate this hierarchy in a top down manner by interactively expanding individual clusters. ASK-GraphView also provides facilities for filtering and coloring, annotation and cluster labeling.

PDF "Ask Graph View", IEEE Transaction on Visualization and Computer Graphics, Vol 12. No 5, 2006
Graph Axes Graph Axes - with C. Tominski and H. Schumann.

We present two novel radial visual arrangements: the TimeWheel and the MultiComb. They are part of an interactive framework called VisAxes which can be used for multidimentional data browsing and analysis.

PDF "Axes Based Visualizations", Symposium in Applied Computing'04
Graph Sketch Graph Sketches - with Irene Finocchi and Jeffrey L. Korn.

We introduce the notion of Graph Sketches. They can be thought of as visual indices that guide the navigation of a multi-graph too large to fit on the available display. We adhere to the Visual Information-Seeking Mantra: Overview first, zoom and filter, then details on demand. Graph Sketches are incorporated into MGV, an integrated visualization and exploration system for massive multi-digraph navigation. We highlight the main algorithmic and visualization tasks behind the computation of Graph Sketches and illustrate several application scenarios. Graph Sketches will be used to guide the navigation of multi-digraphs defined on vertex sets with sizes ranging from 100 to 250 million vertices.

PDF "Graph Sketches", IEEE Symposium on Information Vizualization 2001
Multi_Stars View MGV with Jeffrey L. Korn.

MGV, an integrated visualization and exploration system for massive multidigraph navigation. It adheres to the Visual Information-Seeking Mantra: overview first, zoom and filter, then details on demand. MGV's only assumption is that the vertex set of the underlying digraph corresponds to the set of leaves of a predetermined tree $T$. MGV builds an out-of-core graph hierarchy and provides mechanisms to plug in arbitrary visual representations for each graph hierarchy slice. Navigation from one level to another of the hierarchy corresponds to the implementation of a drill-down interface. In order to provide the user with navigation control and interactive response, MGV incorporates a number of visualization techniques like interactive pixel-oriented 2D and 3D maps, statistical displays, color maps, multilinked views, and a zoomable label based interface. This makes the association of geographic information and graph data very natural. To automate the creation of the vertex set hierarchy for MGV, we use the notion of graph sketches. They can be thought of as visual indices that guide the navigation of a multigraph too large to fit on the available display. MGV follows the client-server paradigm and it is implemented in C and Java-3D. We highlight the main algorithmic and visualization techniques behind the tools and, along the way, point out several possible application scenarios. Our techniques are being applied to multigraphs defined on vertex sets with sizes ranging from 100 million to 250 million vertices.

PDF "A System for Visualizing Massive Multidigraphs", IEEE Transactions on Visualization and Computer Graphics 8(1): 21-38 (2002)
Multi_Comb View Visualizing Massive Multi-Digraphs - with Jeffrey Korn.

MGV is an integrated visualization and exploration system for massive multi-digraph navigation. MGV's only assumption is that the vertex set of the underlying digraph corresponds to the set of leaves of a predetermined tree T. MGV builds an out-of-core graph hierarchy and provides mechanisms to plug in arbitrary visual representations for each graph hierarchy slice. Navigation from one level to another of the hierarchy corresponds to the implementation of a drill-down interface. In order to provide the user with navigation control and interactive response, MGV incorporates a number of visualization techniques like interactive pixel-oriented 2D and 3D maps, statistical displays, multi-linked views, and a zoomable label based interface. This makes the association of geographic information and graph data very natural. MGV follows the client-server paradigm and it is implemented in C and Java-3D. We highlight the main algorithmic and visualization techniques behind the tools and point out along the way several possible application scenarios. Our techniques are being applied to multi-graphs defined on vertex sets with sizes ranging from 100 million to 250 million vertices.

PDF "Visualizing Massive Multi-Digraphs", IEEE Symposium on Information Vizualization 2000
Graph Surface Navigation Graph Surfaces - with Shankar Krishnan.

A broad spectrum of massive data sets can be modeled as dynamic weighted multi-digraphs with sizes ranging from tens of gigabytes to petabytes. The sheer size of these data repositories brings with it interesting visualization and computational challenges. We introduce the notion of graph surfaces as a metaphor that allows the integration of visualization and computation over these data sets. By using out-ofcore algorithms we build a hierarchy of graph surfaces that represents a virtual geography for the data set. In order to provide the user with navigation control and interactive response, we incorporate a number of geometric techniques from 3D computer graphics like terrain triangulation and mesh simplification. We highlight the main algorithmic ideas behind the tools and formulate some novel mathematical problems that have surfaced along the way.

< "Postcript"> "Graph Surfaces", In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems(P. M. Pardalos, Editor), pp. 1-16, 1999, Kluwer Academic Publishers.
Graph_Surface Large-Scale Network Visualization - with E. Koutsofios, E. Gansner and S. North

A multi-disciplinary project investigating visualization and analysis for AT&Tís network and service businesses.

SIGGRAPH Newsletter, August 1999

Algorithm Animation


An Interpreted Algorithm Animation System - with C. Smith.

We present the main elements of a novel algorithm animation system. Algorithms are expressed in a language that resembles textbook set-theoretical descriptions. An animation editor allows a user to express animations via a graphical interface. A language mechanism for binding algorithmic operations to animation actions is provided. By using our own interpreted programming language, more flexible ways to map conceptual-level algorithmic operations to animation actions are possible than with more conventional animation approaches.

< "Postcript"> "An Interpreted Algorithm Animation System", Proc. ICCI'94, 1569-1588 1994 Int. Conf. on Computing and Information, 1994

Disclaimer

The Copyrights of the publications reside with the corresponding publishers.