Published: 2012-11-20
ISBN: 978-91-7519-723-4
ISSN: 1650-3686 (print), 1650-3740 (online)
Previous algorithms for multidimensional scaling; or MDS; aim for scalable performance as the number of points to lay out increases. However; they either assume that the distance function is cheap to compute; and perform poorly when the distance function is costly; or they leave the precise number of distances to compute as a manual tuning parameter. We present Glint; an MDS algorithm framework that addresses both of these shortcomings. Glint is designed to automatically minimize the total number of distances computed by progressively computing a more and more densely sampled approximation of the distance matrix. We present instantiations of the Glint framework on three different classes of MDS algorithms: force-directed; analytic; and gradient-based. We validate the framework through computational benchmarks on several real-world datasets; and demonstrate substantial performance benefits without sacrificing layout quality.
[BG05] BORG I.; GROENEN P. J. F.: Modern Multidimensional Scaling Theory and Applications; 2nd ed. Springer-Verlag; 2005. 29; 31; 35
[BP07] BRANDES U.; PICH C.: Eigensolver methods for progressive multidimensional scaling of large data. In Graph Drawing; Kaufmann M.; Wagner D.; (Eds.); vol. 4372 of Lecture Notes in Computer Science. Springer; 2007; pp. 42–53. 30; 31; 33; 34
[BSL08] BUJA A.; SWAYNE D.; LITTMAN M.; DEAN N.; HOFMANN H.; CHEN L.: Data visualization with multidimensional scaling. Journal of Computational and Graphical Statistics 17; 2 (2008); 444–472. 31
[Cha96] CHALMERS M.: A linear iteration time layout algorithm for visualising high dimensional data. In Proc. IEEE Visualization (1996); pp. 127–132. 31
[dLM09] DE LEEUW J.; MAIR P.: Multidimensional scaling using majorization: SMACOF in R. Journ. Statistical Software 31; 3 (8 2009); 1–30. 31; 33
[dST04] DE SILVA V.; TENENBAUM J.: Sparse multidimensional scaling using landmark points. Technical report; Stanford; 2004. 30; 31
[FC11] FRANCE S.; CARROLL J.: Two-way multidimensional scaling: A review. IEEE Trans. Systems; Man; and Cybernetics; Part C: Applications and Reviews 41; 5 (2011); 644–661. 31
[GKN04] GANSNER E. R.; KOREN Y.; NORTH S. C.: Graph drawing by stress majorization. In Graph Drawing (2004); pp. 239–250. 31
[Gre75] GREEN P.: Marketing applications of mds: Assessment and outlook. The Journal of Marketing (1975); 24–31. 29
[HTF09] HASTIE T.; TIBSHIRANI R.; FRIEDMAN J.: The Elements of Statistical Learning: Data Mining; Inference; and Prediction; Second Edition. Springer Series in Statistics. Springer; 2009. 29
[IMO09] INGRAM S.; MUNZNER T.; OLANO M.: Glimmer: Multilevel MDS on the GPU. IEEE Trans. Visualization and Computer Graphics (TVCG) 15; 2 (2009); 249–261. 29; 30; 31; 33; 34
[IMS12] INGRAM S.; MUNZNER T.; STRAY J.: Hierarchical Clustering and Tagging of Mostly Disconnected Data. Tech. Rep. TR-2012-01; University of British Columbia Department of Computer Science; May 2012. 29
[Ing07] INGRAM S.: Multilevel Multidimensional Scaling on the GPU. Master’s thesis; University of British Columbia Department of Computer Science; 2007. 31; 33
[JCC11] JOIA P.; COIMBRA D.; CUMINATO J. A.; PAULOVICH F. V.; NONATO L. G.: Local affine multidimensional projection. IEEE Transactions on Visualization and Computer Graphics 17; 12 (2011); 2563–2571. 31
[KHKS12] KHOURY M.; HU Y.; KRISHNAN S.; SCHEIDEGGER C.: Drawing large graphs by low-rank stress majorization. Comp. Graph. Forum 31; 3pt1 (June 2012); 975–984. 31
[LMF07] LEWIS J. P.; MCGUIRE M.; FOX P.: Mapping the mental space of game genres. In Proc. ACM SIGGRAPH Symp. Video Games (2007); pp. 103–108. 30; 35
[MPBM03] MATUSIK W.; PFISTER H.; BRAND M.; MCMILLAN L.: A data-driven reflectance model. ACM Trans. Graphics (Proc. SIGGRAPH 2003) 22; 3 (2003); 759–769. 35
[Pla05] PLATT J. C.: FastMap; MetricMap; and Landmark MDS are all Nyström algorithms. In Proc. Intl. Workshop on Artificial Intelligence and Statistics (2005); pp. 261–268. 31
[PSN10] PAULOVICH F.; SILVA C.; NONATO L.: Two-phase mapping for projecting massive data sets. IEEE Trans. Visualization and Computer Graphics 16; 6 (2010); 1281–1290. 31
[RTG00] RUBNER Y.; TOMASI C.; GUIBAS L.: The Earth Mover’s Distance as a metric for image retrieval. Intl. Journ. Computer Vision 40; 2 (2000); 99–121. 30; 35
[RW06] RASMUSSEN C. E.; WILLIAMS C. K. I.: Gaussian Processes for Machine Learning. MIT Press; 2006. 34
[SD74] SPENCE I.; DOMONEY D.: Single subject incomplete designs for nonmetric multidimensional scaling. Psychometrika 39 (1974); 469–490. 30
[SW65] SHAPIRO S.; WILK M.: An analysis of variance test for normality (complete samples). Biometrika 52; 3/4 (1965); 591– 611. 34
[TM08] TERNES D.; MACLEAN K. E.: Designing large sets of haptic icons with rhythm. In Intl. Conf. Haptics: Perception; Devices; and Scenarios (EuroHaptics) (2008); Springer LNCS 5024; pp. 199–208. 30
[Tor52] TORGERSON W.: Multidimensional scaling: I. theory and method. Psychometrika 17 (1952); 401–419. 31
