Technical Reports

The ICICS/CS Reading Room


UBC CS TR-2007-15 Summary

Glimmer: Multilevel MDS on the GPU, June 11, 2007 Stephen Ingram, Tamara Munzner and Marc Olano, 8 pages

We present Glimmer, a new multilevel algorithm for multidimensional scaling that accurately reflects the high-dimensional structure of the original data in the low-dimensional embedding, and converges well. It is designed to exploit modern graphics processing unit (GPU) hardware for a dramatic speedup compared to previous work. We also present GPU-SF, an efficient GPU version of a stochastic force algorithm that we use as a subsystem in Glimmer. We propose robust termination conditions for the iterative GPU-SF computation based the filtered sum of point velocities. Our algorithms can either compute high-dimensional Euclidean distance on the fly from a set of high-dimensional points as input, or handle precomputed distance matrices. The O(N2) size of these matrices would quickly overflow texture memory, so we propose distance paging and distance feeding to remove this scalability restriction. We demonstrate Glimmerís benefits in terms of speed, convergence and correctness against several previous algorithms for a range of synthetic and real benchmark datasets.


If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.