|
|
|
|
 |
|
March 2003, Volume 2, Number 1, Pages 68-77
|
|
|
|
|
Table of contents Previous Full text Next PDF
|
|
|
|
| Original Article |
|
| Fast multidimensional scaling through sampling, springs and interpolation |
|
| Alistair Morrison1, Greg Ross1,2 and Matthew Chalmers1 |
|
1Department of Computing Science, University of Glasgow, Lilybank Gardens, Glasgow, U.K.
|
|
2Greg Ross is supported by a studentship from Nickleby HFE Ltd.
|
|
|
| Abstract |
| The term 'proximity data' refers to data sets within which it is possible to assess the similarity of pairs of objects. Multidimensional scaling (MDS) is applied to such data and attempts to map high-dimensional objects onto low-dimensional space through the preservation of these similarity relations. Standard MDS techniques have in the past suffered from high computational complexity and, as such, could not feasibly be applied to data sets over a few thousand objects in size. Through a novel hybrid approach based upon stochastic sampling, interpolation and spring models, we have designed an algorithm running in O(NÖN). Using Chalmers' 1996 O(N2) spring model as a benchmark for the evaluation of our technique, we compare layout quality and run times using sets of synthetic and real data. Our algorithm executes significantly faster than Chalmers' 1996 algorithm, while producing superior layouts. In reducing complexity and run time, we allow the visualisation of data sets of previously infeasible size. Our results indicate that our method is a solid foundation for interactive and visual exploration of data.
Information Visualization (2003) 2, 68-77. doi:10.1057/palgrave.ivs.9500040 |
|
| Keywords |
| Multidimensional scaling; spring models; hybrid algorithms |
| Received 25 November 2002; revised 2 December 2002; accepted 4 December 2002 |
|
|
Table of contents Previous Full text Next PDF
|
|
|
|
|
