Extreme visualization: squeezing a billion records into a million pixels

ABSTRACT

Database searches are usually performed with query languages and form fill in templates, with results displayed in tabular lists. However, excitement is building around dynamic queries sliders and other graphical selectors for query specification, with results displayed by information visualization techniques. These filtering techniques have proven to be effective for many tasks in which visual presentations enable discovery of relationships, clusters, outliers, gaps, and other patterns. Scaling visual presentations from millions to billions of records will require collaborative research efforts in information visualization and database management to enable rapid aggregation, meaningful coordinated windows, and effective summary graphics. This paper describes current and proposed solutions (atomic, aggregated, and density plots) that facilitate sense-making for interactive visual exploration of billion record data sets.

REFERENCES

• 1: James Abello , Frank van Ham , Neeraj Krishnan, ASK-GraphView: A Large Scale Graph Visualization System, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.669-676, September 2006 [doi>10.1109/TVCG.2006.120]
• 2: Christopher Ahlberg , Ben Shneiderman, Visual information seeking: tight coupling of dynamic query filters with starfield displays, Proceedings of the SIGCHI conference on Human factors in computing systems: celebrating interdependence, p.313-317, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/191666.191775]
• 3: Christopher Ahlberg , Ben Shneiderman, The alphaslider: a compact and rapid selector, Proceedings of the SIGCHI conference on Human factors in computing systems: celebrating interdependence, p.365-371, April 24-28, 1994, Boston, Massachusetts, United States [doi>10.1145/191666.191790]
• 4: Aris, A. and Shneiderman, B., A node aggregation to reduce complexity in network visualizations using semantic substrates, University of Maryland Technical Report, Dept of Computer Science (February 2008).
• 5: Ben Bederson , Jon Meyer, Implementing a zooming user interface: experience building Pad++, Software—Practice & Experience, v.28 n.10, p.1101-1135, Aug. 1998 [doi>10.1002/(SICI)1097-024X(199808)28:10<1101::AID-SPE190>3.0.CO;2-V]
• 6: Buono, P., Aris, A., Plaisant, C., Khella, A., and Shneiderman, B., Interactive pattern search in time series, Proc. SPIE Conference on Visual Data Analysis, SPIE, Washington, DC (January 2005), 175--186.
• 7: Stuart K. Card , Jock D. Mackinlay , Ben Shneiderman, Using vision to think, Readings in information visualization: using vision to think, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 8: Card, S. K. and Nation, D., Degree of Interest Trees: A Component of an Attention-Reactive User Interface, Proc. Advanced Visual Interfaces, Available from ACM Press, New York (2002).
• 9: Chaomei Chen, Top 10 Unsolved Information Visualization Problems, IEEE Computer Graphics and Applications, v.25 n.4, p.12-16, July 2005 [doi>10.1109/MCG.2005.91]
• 10: Eick, S. and Karr, A., Visual Scalability, Journal of Computational and Graphical Statistics 11, 1 (March 2002), 22--43.
• 11: Elmqvist, N., Do, T.-N., Goodell, H., Henry, N., and Fekete, J.-D., ZAME: Interactive Large-Scale Graph Visualization, Proc. IEEE Pacific Visualization Symposium 2008, IEEE Press (March 2008), 215--222.
• 12: Jean-Daniel Fekete , Catherine Plaisant, Interactive Information Visualization of a Million Items, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.117, October 28-29, 2002
• 13: Ying-Huey Fua , Matthew O. Ward , Elke A. Rundensteiner, Hierarchical parallel coordinates for exploration of large datasets, Proceedings of the conference on Visualization '99: celebrating ten years, p.43-50, October 1999, San Francisco, California, United States
• 14: Sudipto Guha , Nick Koudas , Divesh Srivastava, Fast algorithms for hierarchical range histogram construction, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543637]
• 15: Harry Hochheiser , Ben Shneiderman, Dynamic query tools for time series data sets: timebox widgets for interactive exploration, Information Visualization, v.3 n.1, p.1-18, Spring 2004 [doi>10.1145/993176.993177]
• 16: Alfred Inselberg , Bernard Dimsdale, Parallel coordinates: a tool for visualizing multi-dimensional geometry, Proceedings of the 1st conference on Visualization '90, October 23-26, 1990, San Francisco, California
• 17: Daniel A. Keim, Information Visualization and Visual Data Mining, IEEE Transactions on Visualization and Computer Graphics, v.8 n.1, p.1-8, January 2002 [doi>10.1109/2945.981847]
• 18: Daniel A. Keim, Visual exploration of large data sets, Communications of the ACM, v.44 n.8, p.38-44, Aug. 2001 [doi>10.1145/381641.381656]
• 19: Daniel A. Keim, Designing Pixel-Oriented Visualization Techniques: Theory and Applications, IEEE Transactions on Visualization and Computer Graphics, v.6 n.1, p.59-78, January 2000 [doi>10.1109/2945.841121]
• 20: Koren, Y., Carmel, L., and Harel, D., Drawing Huge Graphs by Algebraic Multigrid Optimization, SIAM Multiscale Modeling and Simulation 1, 4 (2003), 645--673.
• 21: Yehuda Koren , Liran Carmel , David Harel, ACE: A Fast Multiscale Eigenvectors Computation for Drawing Huge Graphs, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.137, October 28-29, 2002
• 22: Matthias Kreuseler , Norma Lopez , Heidrun Schumann, A Scalable Framework for Information Visualization, Proceedings of the IEEE Symposium on Information Vizualization 2000, p.27, October 09-10, 2000
• 23: John Lamping , Ramana Rao , Peter Pirolli, A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, Proceedings of the SIGCHI conference on Human factors in computing systems, p.401-408, May 07-11, 1995, Denver, Colorado, United States [doi>10.1145/223904.223956]
• 24: Tamara Munzner, Drawing Large Graphs with H3Viewer and Site Manager, Proceedings of the 6th International Symposium on Graph Drawing, p.384-393, August 01, 1998
• 25: Tamara Munzner , François Guimbretière , Serdar Tasiran , Li Zhang , Yunhong Zhou, TreeJuxtaposer: scalable tree comparison using Focus+Context with guaranteed visibility, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 26: Adam Perer , Ben Shneiderman, Balancing Systematic and Flexible Exploration of Social Networks, IEEE Transactions on Visualization and Computer Graphics, v.12 n.5, p.693-700, September 2006 [doi>10.1109/TVCG.2006.122]
• 27: Catherine Plaisant , Jesse Grosjean , Benjamin B. Bederson, SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation, Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.57, October 28-29, 2002
• 28: Régis Saint-Paul , Guillaume Raschia , Noureddine Mouaddib, General purpose database summarization, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 29: Purvi Saraiya , Chris North , Karen Duca, An Insight-Based Methodology for Evaluating Bioinformatics Visualizations, IEEE Transactions on Visualization and Computer Graphics, v.11 n.4, p.443-456, July 2005 [doi>10.1109/TVCG.2005.53]
• 30: Purvi Saraiya , Chris North , Karen Duca, An Evaluation of Microarray Visualization Tools for Biological Insight, Proceedings of the IEEE Symposium on Information Visualization, p.1-8, October 10-12, 2004 [doi>10.1109/INFOVIS.2004.5]
• 31: Jinwook Seo , Ben Shneiderman, Knowledge Discovery in High-Dimensional Data: Case Studies and a User Survey for the Rank-by-Feature Framework, IEEE Transactions on Visualization and Computer Graphics, v.12 n.3, p.311-322, May 2006 [doi>10.1109/TVCG.2006.50]
• 32: Jinwook Seo , Ben Shneiderman, A rank-by-feature framework for interactive exploration of multidimensional data, Information Visualization, v.4 n.2, p.96-113, July 2005 [doi>10.1057/palgrave.ivs.9500091]
• 33: Ben Shneiderman, Dynamic Queries for Visual Information Seeking, IEEE Software, v.11 n.6, p.70-77, November 1994 [doi>10.1109/52.329404]
• 34: Ben Shneiderman, The Eyes Have It: A Task by Data Type Taxonomy for Information Visualizations, Proceedings of the 1996 IEEE Symposium on Visual Languages, p.336, September 03-06, 1996
• 35: Ben Shneiderman , David Feldman , Anne Rose , Xavier Ferré Grau, Visualizing digital library search results with categorical and hierarchical axes, Proceedings of the fifth ACM conference on Digital libraries, p.57-66, June 02-07, 2000, San Antonio, Texas, United States [doi>10.1145/336597.336637]
• 36: Somayajulu G. Sripada , Ehud Reiter , Jim Hunter , Jin Yu, Generating English summaries of time series data using the Gricean maxims, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956774]
• 37: Chris Stolte , Diane Tang , Pat Hanrahan, Multiscale Visualization Using Data Cubes "InfoVis 2002 Best Paper", Proceedings of the IEEE Symposium on Information Visualization (InfoVis'02), p.7, October 28-29, 2002
• 38: Lida Tang , Ben Shneiderman, Dynamic Aggregation to Support Pattern Discovery: A Case Study with Web Logs, Proceedings of the 4th International Conference on Discovery Science, p.464-469, November 25-28, 2001
• 39: Thomas, J.J. and Cook, K.A. (eds.), Illuminating the Path: Research and Development Agenda for Visual Analytics, IEEE Press (2005).
• 40: Tukey, J. W. and Tukey P. A., Computer graphics and exploratory data analysis: An introduction. Annual Conference and Exposition: Computer Graphics 1985 (Fairfax, VA, USA), National Micrographics Association: Silver Spring; 3 (1985), 773--785.
• 41: Ward, M., Peng, W., and Wang, X., Hierarchical visual data mining for large-scale data, Computational Statistics 19 (2004), 147--158.
• 42: Martin Wattenberg, Visual exploration of multivariate graphs, Proceedings of the SIGCHI conference on Human Factors in computing systems, April 22-27, 2006, Montréal, Québec, Canada [doi>10.1145/1124772.1124891]
• 43: Leland Wilkinson , Anushka Anand , Robert Grossman, Graph-Theoretic Scagnostics, Proceedings of the Proceedings of the 2005 IEEE Symposium on Information Visualization, p.21, October 23-25, 2005 [doi>10.1109/INFOVIS.2005.14]
• 44: Wong, P. C., Foote, H., Mackey, P., Chin Jr., G., Sofia, H., and Thomas, J., A Dynamic Multiscale Magnifying Tool for Exploring Large Sparse Graphs, Information Visualization 7, 2 (June 2008, to appear).
• 45: Beth Yost , Yonca Haciahmetoglu , Chris North, Beyond visual acuity: the perceptual scalability of information visualizations for large displays, Proceedings of the SIGCHI conference on Human factors in computing systems, April 28-May 03, 2007, San Jose, California, USA [doi>10.1145/1240624.1240639]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.5 INFORMATION INTERFACES AND PRESENTATION (I.7)
      H.5.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

General Terms:
Human Factors

Keywords:
aggregation, coordinated windows, database search, density plots, dynamic queries, information visualization, user interface