Incremental board: a grid-based space for visualizing dynamic data sets

ABSTRACT

In Information Visualization, adding and removing data elements can strongly impact the underlying visual space. We introduce a chess board analogy for displaying (projecting) objects from a dynamic set on a 2D space, considering their similarity in a higher dimensional space. Our solution is inherently incremental and maintains a coherent disposition of elements, even for completely renewed sets. The algorithm considers relative positions, rather than raw dissimilarity. It has low computational cost, and its complexity depends only on the size of the currently viewed subset, V. Thus, a set of size N can be sequentially displayed in O(N) time, reaching at most O(N²) only if viewing the whole set at once. Consistent results were obtained as compared to (non-incremental) multidimensional scaling solutions. Moreover, the corresponding visualization is not susceptible to occlusion. The technique was tested in different domains, being particularly adequate to display dynamic corpora.

REFERENCES

• 1: D. Alahakoon, S. Halgamuge, and B. Srinivasan. Dynamic Self-Organizing Maps with Controlled Growth for Knowledge Discovery. IEEE Trans. On Neural Networks, 11(3):601--614, 2000.
• 2: Rasika Amarasiri , Damminda Alahakoon , Kate Smith , Malin Premaratne, HDGSOMr: A High Dimensional Growing Self-Organizing Map Using Randomness for Efficient Web and Text Mining, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.215-221, September 19-22, 2005 [doi>10.1109/WI.2005.70]
• 3: A. Asuncion and D. Newman. UCI machine learning repository. University of California, Irvine, School of Information and Computer Sciences, http://www.ics.uci.edu/~mlearn/MLRepository.html, 2007.
• 4: M. Barioni, E. Botelho, C. Faloutsos, H. Razente, A. Traina, and C. Júnior. Data Visualization in RDBMS. In Proc. IASTED Int. Conf. Information Systems and Databases ISDB, pages 264--269, 2002.
• 5: W. Basalaj. Proximity Visualization of Abstract Data. PhD thesis, University of Cambridge Computer Lab, 2000.
• 6: Benjamin B. Bederson, PhotoMesa: a zoomable image browser using quantum treemaps and bubblemaps, Proceedings of the 14th annual ACM symposium on User interface software and technology, November 11-14, 2001, Orlando, Florida [doi>10.1145/502348.502359]
• 7: J. Blackmore and R. Miikkulainen. Visualizing high-dimensional structure with the incremental grid growing neural network. In Proc. 12th Int. Conf. on Machine Learning, pages 55--63, San Francisco, CA, USA, 1995.
• 8: K. Borner, C. Chen, and K. Boyack. Visualizing Knowledge Domains. Annual Review of Information Science and Technology ARIST, 37:179--255, 2003.
• 9: Matthew Chalmers, A linear iteration time layout algorithm for visualising high-dimensional data, Proceedings of the 7th conference on Visualization '96, p.127-ff., October 28-29, 1996, San Francisco, California, United States
• 10: Chaomei Chen, Information Visualization: Beyond the Horizon, Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 11: Chaomei Chen, CiteSpace II: Detecting and visualizing emerging trends and transient patterns in scientific literature, Journal of the American Society for Information Science and Technology, v.57 n.3, p.359-377, February 2006 [doi>10.1002/asi.v57:3]
• 12: I. T. Jolliffe. Principal component analysis {electronic resource}. Springer, 2002.
• 13: S. Kaski. Data Exploration Using Self-Organizing Maps. PhD thesis, Finnish Academy of Technology, 1997.
• 14: S. Kaski, T. Honkela, K. Lagus, and T. Kohonen. WEBSOM--Self-organizing maps of document collections. Neurocomputing, 21(1-3):101--117, 1998.
• 15: J. Kruskal. Nonmetric multidimensional scaling: A numerical method. Psychometrika, 29(2):115--129, 1964.
• 16: J. Kruskal and M. Wish. Multidimensional Scaling. Sage Publications, 1978.
• 17: J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a nonmetric hypothesis. Psychometrika, 29:1--27, 1964.
• 18: Martin H. C. Law , Anil K. Jain, Incremental Nonlinear Dimensionality Reduction by Manifold Learning, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.28 n.3, p.377-391, March 2006 [doi>10.1109/TPAMI.2006.56]
• 19: M. Law, N. Zhang, and A. Jain. Nonlinear Manifold Learning for Data Stream. Proc. SIAM Data Mining, pages 33--44, 2004.
• 20: Yi Li , Linda G. Shapiro , Jeff A. Bilmes, A Generative/Discriminative Learning Algorithm for Image Classification, Proceedings of the Tenth IEEE International Conference on Computer Vision, p.1605-1612, October 17-20, 2005 [doi>10.1109/ICCV.2005.7]
• 21: A. Lopes, R. Minghim, V. Melo, and F. Paulovich. Mapping texts through dimensionality reduction and visualization techniques for interactive exploration of document collections. Proc. of SPIE, 6060:271--282, 2006.
• 22: A. A. Lopes , R. Pinho , F. V. Paulovich , R. Minghim, Visual text mining using association rules, Computers and Graphics, v.31 n.3, p.316-326, June, 2007 [doi>10.1016/j.cag.2007.01.023]
• 23: Alistair Morrison , Matthew Chalmers, A pivot-based routine for improved parent-finding in hybrid MDS, Information Visualization, v.3 n.2, p.109-122, June 2004 [doi>10.1057/palgrave.ivs.9500069]
• 24: A. Nurnberger and M. Detyniecki. Visualizing changes in data collections using growing self-organizing maps. In Proc. Int. Joint Conf. on Neural Networks IJCNN'02, volume 2, pages 1912--1917, 2002.
• 25: Fernando Vieira Paulovich , Rosane Minghim, Text Map Explorer: a Tool to Create and Explore Document Maps, Proceedings of the conference on Information Visualization, p.245-251, July 05-07, 2006 [doi>10.1109/IV.2006.104]
• 26: Fernando V. Paulovich , Luis G. Nonato , Rosane Minghim , Haim Levkowitz, Least Square Projection: A Fast High-Precision Multidimensional Projection Technique and Its Application to Document Mapping, IEEE Transactions on Visualization and Computer Graphics, v.14 n.3, p.564-575, May 2008 [doi>10.1109/TVCG.2007.70443]
• 27: Fernando V. Paulovich , Maria Cristina F. Oliveira , Rosane Minghim, The Projection Explorer: A Flexible Tool for Projection-based Multidimensional Visualization, Proceedings of the XX Brazilian Symposium on Computer Graphics and Image Processing, p.27-36, October 07-10, 2007 [doi>10.1109/SIBGRAPI.2007.39]
• 28: Kerry Rodden , Wojciech Basalaj , David Sinclair , Kenneth Wood, Evaluating a Visualization of Image Similarity as a Tool for Image Browsing, Proceedings of the 1999 IEEE Symposium on Information Visualization, p.36, October 24-29, 1999
• 29: Kerry Rodden , Wojciech Basalaj , David Sinclair , Kenneth Wood, Does organisation by similarity assist image browsing?, Proceedings of the SIGCHI conference on Human factors in computing systems, p.190-197, March 2001, Seattle, Washington, United States [doi>10.1145/365024.365097]
• 30: J. W. Sammon, A Nonlinear Mapping for Data Structure Analysis, IEEE Transactions on Computers, v.18 n.5, p.401-409, May 1969 [doi>10.1109/T-C.1969.222678]
• 31: James A. Wise, The ecological approach to text visualization, Journal of the American Society for Information Science, v.50 n.13, p.1224-1233, Nov. 1999 [doi>10.1002/(SICI)1097-4571(1999)50:13<1224::AID-ASI8>3.0.CO;2-4]

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
high-dimensional data visualization, multidimensional scaling, projection