User Tools

Site Tools


chicoutimi_2016:implementation_des_doi_graphs_de_van_ham

This is an old revision of the document!


Visual Analytics Course

Instructor: Guy Melançon (email: Guy dot Melancon at labri dot fr)

Chicoutimi Summer 2016 roadmap / Session by session cutdown

DOI trees de George W. Furnas

Dans son article, dont le titre évoque peu ou mal son propos, Furnas développe une approche pour gérer le niveau de détail affiché d'un objet, en fonction du point d'intérêt de l'utilisateur.

C'est l'utilisateur qui manifeste son intérêt pour un élément ou une région des données; c'est le système qui fournit le détail sur cet élément, et un contexte global dans lequel s'inscrit cet élément.

D'autres systèmes laissent à l'utilisateur de gérer et construire le contexte.

Furnas se penche sur la visualisation de documents dont la structure est arborescente.

  • La plupart des documents ont des des chapitres, des sections, titres, des sous-titres, etc.
  • Le code est structuré par blocs imbriqués.

Furnas propose de calculer pour chaque élément de la hiérarchie du document, un indice reflétant son degré d'intérêt DOI (degree of interest). On peut ensuite imposer un seuil au-delà duquel on décide d'afficher l'élément – sinon, soit il est masqué, soit on en affiche un résumé (le titre seul, ou la première ligne, par exemple).

Furnas had a very clever idea applied to the visualization and edition of code. Because code is organized into a hierarchy of blocks, why not only show the headings of a block while the user is not interested in having a detailed look at the details of that block. For instance, only showing the name and signature of a function might be enough, showing the first line of a loop might be sufficient to indicate what the loop is performing at that location in the code.

The left figure show a portion of a file. The right figure show the same file where some blocks have been shrunk to a single line. (Click on the images to access an enlarged view.) So the problem we need to solve is to decide what blocks should be shrunk or not. Observe also that blocks residing within a shrunked blocks will not be shown at all.

Now, we may assume the blocks to form a hierarchy, that is they implicitly defined a tree structure . We may also assume the tree implicitly defines the a priori importance of a node in the tree. That is, a leaf node corresponding to a single instruction is of a lesser importance than an ancestor node corresponding to the function containing this line, for instance. As a consequence, the root node has the greatest a priori importance value.

This leads to define the a priori importance function:

so the a priori importance of a node equals minus its distance to the root in the tree.

Now, suppose the user is editing a particular line in the file. This translate into the fact that a node of the tree momentarily becomes a node of interest. Given a node of interest , we call the focus node, we may compute the distance from any other node to this focus node .

The combination of these two functions may now be used to define what is called the degree of interest of a node (with respect to a focus node ):

Observe how the values distribute in the tree. Nodes with higher values either are closer to the focus node, or have relatively high a priori importance.

Next, we need to threshold the DOI values to obtain a partial view of the tree with more details around the focus node.

/net/html/perso/melancon/Visual_Analytics_Course/data/attic/chicoutimi_2016/implementation_des_doi_graphs_de_van_ham.1464198119.txt.gz · Last modified: 2016/05/25 19:41 by melancon