Composite Rectilinear Deformation for Stretch and Squish Navigation
|
We present the first scalable algorithm that supports the composition of successive rectilinear deformations. Earlier systems that provided stretch and squish navigation could only handle small datasets. More recent work featuring rubber sheet navigation for large datasets has focused on rendering and on application-specific issues. However, no algorithm has yet been presented for carrying out such navigation methods; our paper addresses this problem. For maximum flexibility with large datasets, a stretch and squish navigation algorithm should allow for millions of potentially deformable regions. However, typical usage only changes the extents of a small subset k of these n regions at a time. The challenge is to avoid computations that are linear in n, because a single deformation can affect the absolute screen-space location of every deformable region. We provide an O(k log n) algorithm that supports any application that can lay out a dataset on a generic grid, and show an implementation that allows navigation of trees and gene sequences with millions of items in sub-millisecond time.
[1] 901 D. Auber, Tulip - a huge graph visualization framework. In P. Mutzel and M. Jünger, editors, Graph Drawing Software, Mathematics and Visualization series, pages 105–126. Springer-Verlag, 2003.
[2] D. Beermann, T. Munzner, and G. Humphreys, Scalable, robust visualization of very large trees. In Proc. Eurographics/IEEE Symposium on Visualization (EuroVis 05), pages 37–44, 2005.
[3] M. S. T. Carpendale, D. J. Cowperthwaite, and F. D. Fracchia, 3-dimensional pliable surfaces: for the effective presentation of visual information. In Proc. ACM Symposium on User Interface and Software Technology (UIST 95), pages 217–226, 1995.
[4] T. M. et al. TreeJuxtaposer: Scalable tree comparison using Focus+Context with guaranteed visibility. ACM Trans. on Graphics (Proc. SIGGRAPH 2003), 22 (3): 453–462, 2003.
[5] J.-D. Fekete and C. Plaisant, Interactive information visualization of a million items. In Proc. IEEE Symposium on Information Visualization (InfoVis 02), pages 117–124, 2002.
[6] T. J. Jankun-Kelly, K.-L. Ma, and M. Gertz, A model for the visualization exploration process. In Proc. IEEE Visualization (Vis 02), pages 323–330, 2002.
[7] T. A. Keahey and E. L. Robertson, Nonlinear magnification fields. In Proc. IEEE Symposium on Information Visualization (InfoVis 97), pages 51–58, 1997.
[8] G. G. Robertson and J. D. Mackinlay, The document lens. In Proc. ACM Symposium on User Interface Software and Technology (UIST 93), pages 101–108, 1993.
[9] M. Sarkar and S. P. Reiss, Manipulating screen space with Stretch Tools: Visualizing large structure on small screen. Technical Report CS-92-42, Department of Computer Science, Brown University, Sept. 1992.
[10] M. Sarkar, S. S. Snibbe, O. J. Tversky, and S. P. Reiss, St Stretching the rubber sheet: a metaphor for viewing large layouts on small screens. In Proc. ACM Symposium on User Interface Software and Technology (UIST 93), pages 81–91. ACM Press, 1993.
[11] J. Slack, A partitioned rendering infrastructure for stable accordion navigation. Master's thesis, University of British Columbia Department of Computer Science, 2005.
[12] J. Slack, K. Hildebrand, and T. Munzner, PRISAD: A partitioned rendering infrastructure for scalable accordion drawing. In Proc. IEEE Symposium on Information Visualization (InfoVis 05), pages 41–48, 2005.
[13] J. Slack, K. Hildebrand, and T. Munzner, PRISAD: A partitioned rendering infrastructure for scalable accordion drawing (extended version). Information Visualization 5 (2): 137–151, 2006.
[14] J. Slack, K. Hildebrand, T. Munzner, and K. S. John, SequenceJuxta poser: Fluid navigation for large-scale sequence compariso poser: comparison in context. Proc. German Conference on Bioinformatics, pages 37–42, 2004.
Index Terms:
Focus+Context, information visualization, real time rendering, navigation.
Citation:
James Slack, Tamara Munzner, "Composite Rectilinear Deformation for Stretch and Squish Navigation," IEEE Transactions on Visualization and Computer Graphics, vol. 12, no. 5, pp. 901-908, Sept. 2006, doi:10.1109/TVCG.2006.127
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb