Glint: An MDS Framework for Costly Distance Functions

Stephen Ingram, Tamara Munzner

Abstract | Paper | Software and Data
Diagram of Glint execution.


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.


Glint: An MDS Framework for Costly Distance Functions
Proc. SIGRAD 2012, 29-38

Software and Data

Archive with source code and referenced distance matrix data. → ZIP (12 Mb)

Stephen Ingram
Last modified: Jul 11, 2014