Interactive Visualization and Navigation using the Hyperbolic Space

PD Dr. Jörg Walter
Growing demand for visualization and navigation The demand for techniques handling large collections of data is rapidly growing.
For many tasks of exploratory data analysis visualization plays an important role. It is a key for efficient integration of human expertise -- not only to include his background knowledge, intuition and creativity, but also his powerful pattern recognition and processing capabilities.
The design goals for an optimal user interaction strongly depend on the given visualization task but they certainly include an easy and intuitive navigation with strong support for the user's orientation.
Layout problem for display Since most of available data display devices are two-dimensional -- paper and screens -- the following problem must be solved: finding a meaningful spatial mapping of data onto the display area. One limiting factor is the ``restricted neighborhood'' around a point in a Euclidean 2D surface. Hyperbolic spaces open an interesting loophole.
Hyperbolic Space
unusual properties 		The Hyperbolic Space shows some extraordinary properties which enable us to build novel displays:
  • the neighborhood around each point grows exponential with increasing radius;
  • the hyperbolic space is called more "intensive infinite" than the Euclidean, flat space
Illustration of a patch of H2 embedded into the 3D Euclidean space.

(red) as larger the circle drawn the more wrinkles are included. This illustrates the area growth area(R)=4 PI sinh2(R/2) around each point

(yellow) The local saddle like structure leads to a angle sum deficit in each triangle (<180o). This allows many regular tessellations with triangles.

Most Suitable Projection
Poincaré Disk Model 		The hyperbolic space is a non-euclidean space with negative curvature. There are several projections methods to map the H2 into the display area. For our purpose, the Poincaré Model is the most favorable.
After seeing Coxeter's picture (1957) of the Poincaré projection of the H2, the artist was fascinated by the infinite space covered precisely in the disk:
``A circular regular division of the plane, logically bordered on all sides by the infinitesimal, is something truly beautiful...''.
Note the ``fish-eye'' effect, seen at the fishes: all are of equal size in H2 -- but they appear larger in the center.
Focus+Context The focus can be moved via mouse interaction to each location in H2, like a ``fovea''. The zooming factor is largest in the center and falls gradually off with distance to the fovea. Therefore, the context appears very natural. As more remote things are, the less spatial representation is assigned in the current display.
Moving the focus Via mouse click or drag the Möbius transformation moves the fovea, the focus to the desired location. In the animations you see a regular tessellation grid, where 8 equilateral triangles meet at each vertex. While the grid could be extended to infinity only a subset with four circles of triangles around the center is shown.

Note that straight lines in H2 appear as circle segments. Their extension intersects the unit circle perpendicular. Watch the grid as its appearance changed in a linear (left) and a circular motion (right).
top
In order to employ the visualization capabilities of the H2 the data has to be arranged in the layout space. Today we know three major layout techniques.
In 1994 Lamping and Rao developed the Hyperbolic Tree Viewer at Xerox Parc and demonstrated the remarkable navigation features in the hyperbolic space (see star tree at inxight.com for H2 and Munzner for a H3 version)
Required data type:
tree-like graph data
Key ideas:
Hyperbolic Tree Layout (HTL) is a recursive partitioning of the space by the nodes (and their children).

The question how effective is visualization and navigation in the hyperbolic space was studied by Pirolli et al. (2001, see ref in literature). By conducting eye-tracker experiments they found that the focus+context navigation can significantly accelerate information foraging. Risden et al. (2000) compared traditional and hyperbolic browsers and found significant improvement in task time for this novel display type.


The Hyperbolic Self-Organizing Maps (HSOM) is the transfer of Kohonen's SOM algorithm operating on a finite grid structure in H2.
Required data type:
vectorial data
Key ideas:
find a cluster structure which is assigned to the nodes of an H2 grid. The process is data driven (``self-organizing'') and topology preserving, i.e. similar objects are mapped to nearby nodes.

The HSOM is most useful to visualize coarse grain, overview map of large collections of data, since it can handle large amounts of objects (e.g. documents with the TFIDF-scheme). ..see more on visualizing texts and semantic browsing with HSOM and with a novel hybrid architecture.


The Hyperbolic Multidimensional Scaling (HMDS) is the conceptual combination of Sammon's Multidimensional Scaling algorithm and the Poincaré Model of the hyperbolic plane.
Key ideas:
find a accommodation of the data objects which resembles the dissimilarity structure of the data as much as possible.
Required data type:
pairwise dissimilarity data (can be considered most general)
Map Metaphore We are very much used to visualizing structure using the map metaphore. I.e. similarity between data objects in the display are reflected in their spatial arrangement. All the above layout techniques provide this property. For a further comparison and discussion see the ICDM 2003 paper.
top
HMDS Introduction
Hybrid Hyperbolic Data Viewer (HHDV, combining HSOM and HMDS)
Multimedia Application (HIB)
Other Links
  • More on the HSOM grid approach here

  • More on visualizing trees, e.g. demo and Munzner
$Revision: 1.1 $