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. Abello, J., van Ham, F., and Krishnan, N., ASK-GraphView: A Large Scale Graph Visualization System, IEEE Trans. Visualization & Computer Graphics 12, 5 (2006), 669--676.
2. Ahlberg, C. and Shneiderman, B., Visual Information Seeking: Tight Coupling of Dynamic Query Filters with Starfield Display. Conference proceedings on Human factors in computing systems, April 1994, 313--318, ACM New York.
3. Ahlberg, C. and Shneiderman, B., AlphaSlider: A compact and rapid selector, Proc. of ACM CHI94 Conference, ACM Press, New York (April 1994), 365--371.
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. Bederson, B. B., & Meyer, J., Implementing a Zooming User Interface: Experience Building Pad++, Software: Practice and Experience, 28, 10 (1998), 1101--1135.
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. Card, S. K., MacKinlay, J. D., Shneiderman, B., Readings in Information Visualization: Using Vision to Think, Morgan Kaufmann Publishers, 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. Chen, C., Top 10 Unsolved Information Visualization Problems, IEEE Computer Graphics & Applications (July/August 2005), 12--16.
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. Fekete, J.-D., Plaisant, C., Interactive Information Visualization of a Million Items, Proc. IEEE Symposium on Information Visualization 2002 (InfoVis 2002, Boston, USA), IEEE Press, Los Alamitos, CA (October 2002), 117--124.
13. Fua, Y.-H., Ward, M., and Rundensteiner, E., Hierarchical Parallel Coordinates for Exploration of Large Datasets, Proc. IEEE Visualization'99, IEEE Press, Los Alamitos, CA (1999), 43--50.
14. Guha, S., Koudas, N., and Srivastava, D., Fast algorithms for hierarchical range histogram construction, Proc. ACM Symposium on Principles of Database Systems, ACM Press, New York (2002), 180--187.
15. Hochheiser, H. and Shneiderman, B., Dynamic query tools for time series data sets, Timebox widgets for interactive exploration, Information Visualization 3, 1 (March 2004), 1--18.
16. Inselberg, A. and Dimsdale, B., Parallel coordinates: A tool for visualizing multidimensional geometry, Proc. Visualization'90 (San Francisco, Oct. 23-26). IEEE Press, Los Alamitos, CA (1990), 361--370.
17. Keim, D. A., Information Visualization and Visual Data Mining, IEEE Transactions on Visualization and Computer Graphics 8, 1 (January 2002), 1--8.
18. Keim, D. A., Visual Exploration of Large Data Sets, Communications of the ACM 44, 8 (August 2001), 38--44.
19. Keim, D. A., Designing Pixel-Oriented Visualization Techniques: Theory and Applications, IEEE Trans. on Visualization and Computer Graphics 6, 1 (January 2000), 59--78. {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. Koren, Y., Carmel, L., and Harel, D., ACE: A Fast Multiscale Eigenvector Computation for Drawing Huge Graphs, Proc. IEEE Information Visualization 2002 (InfoVis'02) 2002), 137--144.
22. Kreuseler, M., Lopez, N., and Schumann, H., A. scalable framework for information visualization, Proc. IEEE Symposium on Information Visualization (2000), 27--36.
23. Lamping, J., Rao, R., and Pirolli, P., A focus+context technique based on hyperbolic geometry for visualizing large hierarchies, Proc. of ACM CHI95 Conference, ACM Press, New York (1995), 401--408.
24. Munzner, T., Drawing Large Graphs with H3Viewer and Site Manager, Proc. Symp. Graph Drawing'98 (1998): 384--393.
25. Munzner, T., Guimbretiere, F., Tasiran, S., Zhang, L., and Zhou, Y., TreeJuxtaposer: Scalable Tree Comparison using Focus+Context with Guaranteed Visibility, ACM Trans. on Graphics 22, 3 (2002), 453--462.
26. Perer, A. and Shneiderman, B., Balancing systematic and flexible exploration of social networks, IEEE Symposium on Information Visualization and IEEE Transactions on Visualization and Computer Graphics 12, 5 (October 2006), 693--700.
27. Plaisant, C., Grosjean, J., Bederson, B., SpaceTree: Supporting Exploration in Large Node Link Tree, Design Evolution and Empirical Evaluation, IEEE Symposium on Information Visualization (2002), 57--64.
28. Saint-Paul, R., Raschia, G., and Mouaddib, N., General purpose database summarization, Proc. 31st International Conference on Very Large Data Bases, Trondheim, Norway (August 30-September 02, 2005), 733--744.
29. Saraiya, P., North, C., and Duca, K., An Insight-Based Methodology for Evaluating Bioinformatics Visualization, IEEE Trans. Visualization and Computer Graphics 11, 4 (July/Aug. 2005).
30. Saraiya, P., North, C., and Duca, K., An Evaluation of Microarray Visualization Tools for Biological Insight", IEEE Symposium on Information Visualization 2004 (InfoVis 2004) (2004), 1--8.
31. Seo, J. and Shneiderman, B., 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 12, 3 (May/June, 2006), 311--322.
32. Seo, J. and Shneiderman, B., A rank-by-feature framework for interactive exploration of multidimensional data, Information Visualization 4, 2 (June 2005), 99--113.
33. Shneiderman, B., Dynamic queries for visual information seeking, IEEE Software, 11, 6 (1994), 70--77.
34. Shneiderman, B., The eyes have it: A task by data-type taxonomy for information visualizations, Proc. Visual Languages (Boulder, CO, Sept. 3-6). IEEE Computer Science Press, Los Alamitos, CA (1996), 336--343.
35. Shneiderman, B., Feldman, D., Rose, A., and Ferre, X. A., Visualizing digital library search results with categorical and hierarchical axes, Proc. 5th ACM International Conference on Digital Libraries, ACM, New York (June 2000), 57--66.
36. Sripada, S. G., Reiter, E., Hunter, J., and Yu, J., Generating English Summaries of Time Series Data using the Gricean Maxims, Proc. ACM Conference on Knowledge Discovery and Data Mining (KDD) (2003), 187--196.
37. Stolte, C., Tang, D., and Hanrahan, P., Multiscale visualization using data cubes, Proc. Eighth IEEE Symposium on Information Visualization, Boston, MA (October 2002), 7--14.
38. Tang, L. and Shneiderman, B., Dynamic aggregation to support pattern discovery: A case study with web logs, Proc. Discovery Science: 4th International Conference 2001, Editors (Jantke, K. P. and Shinohara, A.), Springer-Verlag, Berlin (March 2001), 464--469.
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. Wattenberg, M., Visual Exploration of Multivariate Graphs, Proc. ACM SIGCHI Conference on Human Factors in Computing Systems, ACM Press, New York (2006), 811--819.
43. Wilkinson, L., Anand, A., and Grossman, R., Graph-theoretic scagnostics, Proc. IEEE Information Visualization 2005 (INFOVIS'05) (2005), 157--164.
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. Yost, B., Haciahmetoglu, Y., and North, C., Beyond visual acuity: the perceptual scalability of information visualizations for large displays, Proc. ACM SIGCHI Conference on Human Factors in Computing Systems, San Jose, California, USA (April 28-May 03, 2007), 101--110.

Index Terms

• Human-centered computing

• Information systems

  • Data management systems