Home | About Us | Contact Us | Site Map | FAQs

¹Department of Computing Science, University of Glasgow, Glasgow, U.K.

Correspondence to: Alistair Morrison, Department of Computing Science, University of Glasgow, Lilybank Gardens, Glasgow G12 8QQ, U.K. Tel: +44 141 330 3339; Fax: +44 141 330 4913; E-mail: morrisaj@dcs.gla.ac.uk

^†Portions reprinted, with permission from Morrison and Chalmers.¹ (c) 2003 IEEE.

The problem of exploring or visualising data of high dimensionality is central to many tools for information visualisation. Through representing a data set in terms of inter-object proximities, multidimensional scaling may be employed to generate a configuration of objects in low-dimensional space in such a way as to preserve high-dimensional relationships. An algorithm is presented here for a heuristic hybrid model for the generation of such configurations. Building on a model introduced in 2002, the algorithm functions by means of sampling, spring model and interpolation phases. The most computationally complex stage of the original algorithm involved the execution of a series of nearest-neighbour searches. In this paper, we describe how the complexity of this phase has been reduced by treating all high-dimensional relationships as a set of discretised distances to a constant number of randomly selected items: pivots. In improving this computational bottleneck, the algorithmic complexity is reduced from to O(N^5/4). As well as documenting this improvement, the paper describes evaluation with a data set of 108,000 13-dimensional items and a set of 23,141 17-dimensional items. Results illustrate that the reduction in complexity is reflected in significantly improved run times and that no negative impact is made upon the quality of layout produced.

Information Visualization (2004) 3, 109-122. doi:10.1057/palgrave.ivs.9500069
Published online 20 May 2004

multidimensional scaling; MDS; hybrid algorithms; force-directed placement; spring models; pivots; near-neighbour search