Article

Scalable, robust visualization of very large trees

Authors:

Tamara Munzner,

Greg HumphreysAuthors Info & Claims

EUROVIS'05: Proceedings of the Seventh Joint Eurographics / IEEE VGTC conference on Visualization

Pages 37 - 44

Published: 01 June 2005 Publication History

Abstract

The TreeJuxtaposer system [MGT*03] allowed visual comparison of large trees with guaranteed visibility of landmarks and Focus+Context navigation. While that system allowed exploration and comparison of larger datasets than previous work, it was limited to a single tree of 775,000 nodes by a large memory footprint. In this paper, we describe the theoretical limitations to TreeJuxtaposer's architecture that severely restrict its scalability. We provide two scalable, robust solutions to these limitations: TJC and TJC-Q. TJC is a system that supports browsing trees up to 15 million nodes by exploiting leading-edge graphics hardware while TJC-Q allows browsing trees up to 5 million nodes on commodity platforms. Both of these systems use a fast new algorithm for drawing and culling and benefit from a complete redesign of all data structures for more efficient memory usage and reduced preprocessing time.

References

[1]

ANCESTRY WORLD TREE:. http://www.ancestry.com/trees, cited April 9 2004. 1

[2]

ARCHITECTURAL REVIEW BOARD: ARB ATI_draw_buffers Specification, Dec 2002. 5

[3]

CHOI J.-H., JUNG H.-Y., KIM H.-S., CHO H.-G.: PhyloDraw: A phylogenetic tree drawing system. Bioinformatics 16, 11 (2000), 1056-1058. 2

[4]

CARD S. K., NATION D.: Degree-ofinterest trees: A component of an attentionreactive user interface. In Proc. Advanced Visual Interfaces (AVI) (2002), pp. 231-245. 1, 3

Digital Library

[5]

FEKETE J.-D., PLAISANT C.: Interactive information visualization of a million items. In Proc. InfoVis (2002), pp. 117-124. 2

Digital Library

[6]

HERMAN, MELANÇON G., MARSHALL M. S.: Graph visualization and navigation in information visualization: A survey. IEEE Trans. Visualization and Computer Graphics 6, 1 (2000), 24-43. 2

Digital Library

[7]

LAMPING J., RAO R., PIROLLI P.: A Focus+Content Technique Based on Hyperbolic Geometry for Viewing Large Hierarchies. In Proc. CHI '95 (1995), pp. 401-408. 1, 2

Digital Library

[8]

MUNZNER T., GUIMBRETIÈRE F., TASIRAN S., ZHANG L., ZHOU Y.: TreeJuxtaposer: Scalable tree comparison using Focus+Context with guaranteed visibility. ACM Trans. Graph. (SIGGRAPH) 22, 3 (2003), 453-462. 1, 2, 3, 4

Digital Library

[9]

MUNZNER T.: Drawing Large Graphs with H3Viewer and Site Manager. In Proc. Graph Drawing, LNCS 1547 (1998), Springer-Verlag, pp. 384-393. 1, 2

Digital Library

[10]

PENNISI E.: Modernizing the tree of life. Science 300, 5626 (13 June 2003), 1692. 1697. 1

[11]

PLAISANT C., GROSJEAN J., BEDERSON B.: Space Tree: Design evolution of a node link tree browser. In Proc. InfoVis (2002), pp. 57-64. 1, 3

[12]

QU H., KAUFMAN A. E.: O-buffer: A framework for sample-based graphics. IEEE Trans. Vis. Comput. Graph. 10, 4 (2004), 410-421. 5

Digital Library

[13]

ROST U., BORNBERG-BAUER E.: Treewiz: interactive exploration of huge trees. Bioinformatics 18, 1 (2002), 109-114. 2

[14]

SILICON GRAPHICS INC.: Standard Template Library Programmer's Guide, 1994. 6

[15]

SARKAR M., SNIBBE S. S., TVERSKY O. J., REISS S. P.: Stretching the Rubber Sheet: A Metaphor for Viewing Large Layouts on Small Screens. In Proc. User Interface Software and Technologies (UIST) (1993), pp. 81-91. 2

Digital Library

[16]

THÉRY L., BERTOT Y., KAHN G.: Real theorem provers deserve real user-interfaces. In Proc. 5th SIGSOFT Symp. on Software Development Environments (1992). 1

Digital Library

[17]

VAN WIJK J. J., VAN DE WETERING H.: Cushion treemaps. In Proc. InfoVis (1999), pp. 73-78. 2

Cited By

Karloff HShirley KScheuermann G(2013)Maximum entropy summary treesProceedings of the 15th Eurographics Conference on Visualization10.1111/cgf.12094(71-80)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1111/cgf.12094
Robertson GEbert DEick SKeim DJoy K(2009)Scale and complexity in visual analyticsInformation Visualization10.1057/ivs.2009.238:4(247-253)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1057/ivs.2009.23
Zaslavsky LBao YTatusova T(2007)An adaptive resolution tree visualization of large influenza virus sequence datasetsProceedings of the 3rd international conference on Bioinformatics research and applications10.5555/1759681.1759699(192-202)Online publication date: 7-May-2007
https://dl.acm.org/doi/10.5555/1759681.1759699
Show More Cited By

Index Terms

Scalable, robust visualization of very large trees
1. Computing methodologies
  1. Computer graphics

Recommendations

Visualization of multivariate data with tail trees

We introduce graphical tools to visualize the shape, the location, and the orientation of a multivariate data set. We define a tree structure among the observations, called a tail tree. A tail tree is a tree whose root node corresponds to a center point ...
Rank-Balanced Trees

Since the invention of AVL trees in 1962, many kinds of binary search trees have been proposed. Notable are red-black trees, in which bottom-up rebalancing after an insertion or deletion takes O(1) amortized time and O(1) rotations worst-case. But the ...
A visualization tool for interactive learning of large decision trees
ICTAI '00: Proceedings of the 12th IEEE International Conference on Tools with Artificial Intelligence

Abstract: Decision tree induction is certainly among the most applicable learning techniques due to its power and simplicity. However learning decision trees from large datasets, particularly in data mining, is quite different from learning from small ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EUROVIS'05: Proceedings of the Seventh Joint Eurographics / IEEE VGTC conference on Visualization

June 2005

310 pages

ISBN:3905673193

Editors:
Ken Brodlie
University of Leeds, UK
,
David Duke
University of Leeds, UK
,
Ken Joy
UC Davis

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 01 June 2005

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Karloff HShirley KScheuermann G(2013)Maximum entropy summary treesProceedings of the 15th Eurographics Conference on Visualization10.1111/cgf.12094(71-80)Online publication date: 17-Jun-2013
https://dl.acm.org/doi/10.1111/cgf.12094
Robertson GEbert DEick SKeim DJoy K(2009)Scale and complexity in visual analyticsInformation Visualization10.1057/ivs.2009.238:4(247-253)Online publication date: 1-Dec-2009
https://dl.acm.org/doi/10.1057/ivs.2009.23
Zaslavsky LBao YTatusova T(2007)An adaptive resolution tree visualization of large influenza virus sequence datasetsProceedings of the 3rd international conference on Bioinformatics research and applications10.5555/1759681.1759699(192-202)Online publication date: 7-May-2007
https://dl.acm.org/doi/10.5555/1759681.1759699
Slack JMunzner T(2006)Composite Rectilinear Deformation for Stretch and Squish NavigationIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2006.12712:5(901-908)Online publication date: 1-Sep-2006
https://dl.acm.org/doi/10.1109/TVCG.2006.127

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents