Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies

ABSTRACT

Treemaps, a space-filling method for visualizing large hierarchical data sets, are receiving increasing attention. Several algorithms have been previously proposed to create more useful displays by controlling the aspect ratios of the rectangles that make up a treemap. While these algorithms do improve visibility of small items in a single layout, they introduce instability over time in the display of dynamically changing data, fail to preserve order of the underlying data, and create layouts that are difficult to visually search. In addition, continuous treemap algorithms are not suitable for displaying fixed-sized objects within them, such as images.This paper introduces a new "strip" treemap algorithm which addresses these shortcomings, and analyzes other "pivot" algorithms we recently developed showing the trade-offs between them. These ordered treemap algorithms ensure that items near each other in the given order will be near each other in the treemap layout. Using experimental evidence from Monte Carlo trials and from actual stock market data, we show that, compared to other layout algorithms, ordered treemaps are more stable, while maintaining relatively favorable aspect ratios of the constituent rectangles. A user study with 20 participants clarifies the human performance benefits of the new algorithms. Finally, we present quantum treemap algorithms, which modify the layout of the continuous treemap algorithms to generate rectangles that are integral multiples of an input object size. The quantum treemap algorithm has been applied to PhotoMesa, an application that supports browsing of large numbers of images.

REFERENCES

• 1: Baker, M. J. and Eick, S. G. 1995. Space-filling software visualization. J. Vis. Lang. Comput., 6, 119--133.
• 2: Benjamin B. Bederson, PhotoMesa: a zoomable image browser using quantum treemaps and bubblemaps, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502359]
• 3: Bruls, M., Huizing, K., and van Wijk, J. J. 2000. Squarified treemaps. In Proceedings of Joint Eurographics and IEEE TCVG Symposium on Visualization (TCVG 2000) IEEE Press, pp. 33--42.
• 4: Edgar, G. A., Ewing, J. H., and Gehring, F. W. 1995. Measure, Topology, and Fractal Geometry. Springer Verlag.
• 5: Fekete, J.-D. and Plaisant, C. 2002. Interactive Information Visualization to the Million. Tech. Rep. CS-TR-4320, Computer Science Department, University of Maryland, College Park, MD.
• 6: Anthony J. Hornof, Visual search and mouse-pointing in labeled versus unlabeled two-dimensional visual hierarchies, ACM Transactions on Computer-Human Interaction (TOCHI), v.8 n.3, p.171-197, September 2001 [doi>10.1145/502907.502908]
• 7: Liqun Jin , David C. Banks, TennisViewer: A Browser for Competition Trees, IEEE Computer Graphics and Applications, v.17 n.4, p.63-65, July 1997 [doi>10.1109/38.595272]
• 8: Brian Scott Johnson, Treemaps: visualizing hierarchical and categorical data, University of Maryland at College Park, College Park, MD, 1993
• 9: Jungmeister, W.-A. and Turo, D. 1992. Adapting Treemaps to Stock Portfolio Visualization. Tech. Rep. CS-TR-2996, Computer Science Department, University of Maryland, College Park, MD.
• 10: Smartmoney Marketmap 2002. http://www.smartmoney.com/marketmap.
• 11: Sheldon, R. A. 1997. A First Course in Probability. Englewood Cliffs, NJ: Prentice Hall.
• 12: Ben Shneiderman, Tree visualization with tree-maps: 2-d space-filling approach, ACM Transactions on Graphics (TOG), v.11 n.1, p.92-99, Jan. 1992 [doi>10.1145/102377.115768]
• 13: Ben Shneiderman , Martin Wattenberg, Ordered Treemap Layouts, Proceedings of the IEEE Symposium on Information Visualization 2001 (INFOVIS'01), p.73, October 22-23, 2001
• 14: David Turo , Brian Johnson, Improving the visualization of hierarchies with treemaps: design issues and experimentation, Proceedings of the 3rd conference on Visualization '92, October 19-23, 1992, Boston, Massachusetts
• 15: Vernier, F. and Nigay, L. 2000. Modifiable treemaps containing variable-shaped units. In Proceedings of Extended Abstracts of IEEE Information Visualization (InfoVis 2000) New York: IEEE, pp. 28--35.
• 16: Martin Wattenberg, Visualizing the stock market, CHI '99 extended abstracts on Human factors in computing systems, May 15-20, 1999, Pittsburgh, Pennsylvania [doi>10.1145/632716.632834]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.2 User/Machine Systems
          Subjects: Human factors
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.2 User Interfaces (D.2.2, H.1.2, I.3.6)
          Subjects: Graphical user interfaces (GUI); Screen design (e.g., text, graphics, color)

General Terms:
Algorithms, Design, Human Factors

Keywords:
Hierarchies, human-computer interaction, image browsers, information visualization, jazz, ordered treemaps, treemaps, trees, zoomable user interfaces (ZUIs).