ABSTRACT
Structural comparison of large trees is a difficult task that is only partially supported by current visualization techniques, which are mainly designed for browsing. We present TreeJuxtaposer, a system designed to support the comparison task for large trees of several hundred thousand nodes. We introduce the idea of "guaranteed visibility", where highlighted areas are treated as landmarks that must remain visually apparent at all times. We propose a new methodology for detailed structural comparison between two trees and provide a new nearly-linear algorithm for computing the best corresponding node from one tree to another. In addition, we present a new rectilinear Focus+Context technique for navigation that is well suited to the dynamic linking of side-by-side views while guaranteeing landmark visibility and constant frame rates. These three contributions result in a system delivering a fluid exploration experience that scales both in the size of the dataset and the number of pixels in the display. We have based the design decisions for our system on the needs of a target audience of biologists who must understand the structural details of many phylogenetic, or evolutionary, trees. Our tool is also useful in many other application domains where tree comparison is needed, ranging from network management to call graph optimization to genealogy.
Supplemental Material
- ADAMS, E. N. 1972. Consensus techniques and the comparison of taxonomic trees. Systematic Zoology 21, 390--397.Google ScholarCross Ref
- AMENTA, N., AND KLINGNER, J. 2002. Case study: Visualizing sets of evolutionary trees. In Proc. InfoVis 2002. Google ScholarDigital Library
- ASIMOV, D. 1985. The grand tour: a tool for viewing multidimensional data. SIAM J. Sci. Statist. Computing 6, 1, 128--143. Google ScholarDigital Library
- BARTRAM, L., HO, A., DILL, J., AND HENIGMAN, F. 1995. The continuous zoom: A constrained fisheye technique for viewing and navigating large information spaces. In Proc. UIST '95, 207--215. Google ScholarDigital Library
- BECKER, R. A., AND CLEVELAND, W. S. 1987. Brushing scatterplots. Technometrics 29, 127--142. Reprinted in Dynamic Graphics for Data Analysis, W. S. Cleveland and M. E. McGill eds., Chapman and Hall, New York, (1988). Google ScholarDigital Library
- BRODER, A. Z., GLASSMAN, S. C., MANASSE, M. S., AND ZWEIG, G. 1997. Syntactic clustering of theWeb. In Proc. Sixth International World Wide Web Conference, 391--404. Google ScholarDigital Library
- BRODER, A. Z. 1998. On the resemblance and containment of documents. In SEQS: Sequences, 21--29. Google ScholarDigital Library
- CARD, S. K., AND NATION, D. 2002. Degree-of-interest trees: A component of an attention-reactive user interface. In Proc. Advanced Visual Interfaces (AVI 2002). Google ScholarDigital Library
- CHI, E. H., AND CARD, S. K. 1999. Sensemaking of evolving web sites using visualization spreadsheets. In Proc. InfoVis 1999, 18--25. Google ScholarDigital Library
- CHI, E. H., PITKOW, J., MACKINLAY, J., PIROLLI, P., GOSSWEILER, R., AND CARD, S. K. 1998. Visualizing the evolution of web ecologies. In Proc. of ACM CHI 98 Conference on Human Factors in Computing Systems, 400--407. Google ScholarDigital Library
- DAY, W. H. E. 1985. Optimal algorithms for comparing trees with labeled leaves. Journal of Classification 2, 7--28.Google ScholarCross Ref
- FURNAS, G. W. 1997. Effective view navigation. In Proc. SIGCHI 97. Google ScholarDigital Library
- GRAHAM, M., AND KENNEDY, J. 2001. Combining linking & focusing techniques for a multiple hierarchy visualisation. In 5th Int'l Conf. on Information Visualisation - IV2001, University of London, IEEE Computer Society Press, 425--432. Google ScholarDigital Library
- GUIMBRETIÈRE, F. 2001. Fluid interaction for high-resolution wall-size displays. PhD thesis, Stanford University.Google Scholar
- HAREL, D., AND TARJAN, R. E. 1984. Fast algorithms for finding nearest common ancestors. SIAM Journal of Computing 13, 338--355. Google ScholarDigital Library
- HERMAN, MELANÇON, G., AND MARSHALL, M. S. 2000. Graph visualization and navigation in information visualization: A survey. IEEE Transactions on Visualization and Computer Graphics 6, 1, 24--43. Google ScholarDigital Library
- JUL, S., AND FURNAS, G. W. 1998. Critical Zones in Desert Fog: Aids to Multiscale Navigation. In Proc. UIST '98, 97--106. Google ScholarDigital Library
- LAMPING, J., RAO, R., AND PIROLLI, P. 1995. A Focus+Content Technique Based on Hyperbolic Geometry for Viewing Large Hierarchies. In Proc. CHI '95, 401--408. Google ScholarDigital Library
- LYNCH, K. 1960. Image of the City. MIT Press.Google Scholar
- MADDISON, D., AND MADDISON, W., 1992. MacClade: Analysis of phylogeny and character evolution.Google Scholar
- MARGUSH, T., AND MCMORRIS, F. R. 1981. Consensus n-trees. Bulletin of Mathematical Biology 3, 239--244.Google Scholar
- MÖLLAR, T., AND HAINES, E. 1999. Real-Time Rendering. AK Peters. Google ScholarDigital Library
- MUNZNER, T. 1998. Drawing Large Graphs with H3Viewer and Site Manager. In Proc. Graph Drawing '98, Lecture Notes in Comp. Sci. 1547, Springer-Verlag, 384--393. Google ScholarDigital Library
- MUNZNER, T. 2000. Interactive Visualization of Large Graphs and Networks. PhD thesis, Stanford University. Google ScholarDigital Library
- NEUFELD, E., KUSALIK, A. J., AND DOBROHOCZKI, M. 1997. Visual metaphors for understanding logic program execution. In Graphics Interface '97. Google ScholarDigital Library
- PLAISANT, C., GROSJEAN, J., AND BEDERSON, B. 2002. SpaceTree: Design evolution of a node link tree browser. In Proc. InfoVis 2002.Google Scholar
- PREPARATA, F. P., AND SHAMOS, M. I. 1990. Computational Geometry: An Introduction, 3rd ed. Springer-Verlag. Google ScholarDigital Library
- ROBERTSON, G. G., AND MACKINLAY, J. D. 1993. The document lens. In Proc. UIST '93. Google ScholarDigital Library
- ROBERTSON, G., MACKINLAY, J., AND CARD, S. 1991. Cone Trees: Animated 3D Visualizations of Hierarchical Information. In Proc. SIGCHI '91, 189--194. Google ScholarDigital Library
- ROBINSON, D. F., AND FOULDS, L. R. 1981. Comparison of phylogenetic trees. Mathematical Biosience 53, 131--147.Google ScholarCross Ref
- ROST, U., AND BORNBERG-BAUER, E. 2002. Treewiz: interactive exploration of huge trees. Bioinformatics 18, 1, 109--114.Google ScholarCross Ref
- SARKAR, M., SNIBBE, S. S., TVERSKY, O. J., AND REISS, S. P. 1993. Stretching the Rubber Sheet: A Metaphor for Viewing Large Layouts on Small Screens. In Proc. UIST '93, 81--91. Google ScholarDigital Library
- SEO, J., AND SHNEIDERMAN, B. 2002. Interactively exploring hierarchical clustering results. IEEE Computer 35, 7 (July), 80--86. Google ScholarDigital Library
- SHIVAKUMAR, N., AND GARCÍA-MOLINA, H. 1995. SCAM: A copy detection mechanism for digital documents. In Proc. 2nd Annual Conf. on Theory and Practice of Digital Libraries. Google ScholarDigital Library
- SOKAL, R. R., AND ROHLF, F. J. 1981. Taxonomic congruence in the Leptopodomorpha re-examined. Systematic Zoology 30, 309--325.Google ScholarCross Ref
- SWOFFORD, D. L., 1998. PAUP* 4.0 - Phylogenetic Analysis Using Parsimony (*and Other Methods).Google Scholar
- TORBORG, J., AND KAJIYA, J. T. 1996. Talisman: Commodity realtime 3D graphics for the PC. In SIGGRAPH 96, 57--68. Google ScholarDigital Library
- WARD, M. O., AND MARTIN, A. R. 1995. High dimensional brushing for interactive exploration of multivariate data. In Proc. IEEE Visualization '95, 271--278. Google ScholarDigital Library
- ZHANG, L. 2003. On matching nodes between trees. Tech. Rep. 2003-67, HP Labs.Google Scholar
Index Terms
- TreeJuxtaposer: scalable tree comparison using Focus+Context with guaranteed visibility
Recommendations
TreeJuxtaposer: scalable tree comparison using Focus+Context with guaranteed visibility
Structural comparison of large trees is a difficult task that is only partially supported by current visualization techniques, which are mainly designed for browsing. We present TreeJuxtaposer, a system designed to support the comparison task for large ...
Degree-of-interest trees: a component of an attention-reactive user interface
AVI '02: Proceedings of the Working Conference on Advanced Visual InterfacesThis paper proposes Degree-of-Interest trees. These trees use degree-of-interest calculations and focus+context visualization methods, together with bounding constraints, to fit within pre-established bounds. The method is an instance of an emerging "...
Multi-con: exploring graphs by fast switching among multiple contexts
AVI '10: Proceedings of the International Conference on Advanced Visual InterfacesFocus+Context is a popular and effective technique for graph exploration. While previous works concentrate on studying how to display focal nodes with a single context, we argue that it is often difficult to select an optimal context for a complex graph ...
Comments