A linear iteration time layout algorithm for visualising high-dimensional data

A technique is presented for the layout of high dimensional data in a low dimensional space. This technique builds upon the force based methods that have been used previously to make visualisations of various types of data such as bibliographies and sets of software modules. The canonical force based model, related to solutions of the N body problem, has a computational complexity of O(N ²) per iteration. The paper presents a stochastically based algorithm of linear complexity per iteration which produces good layouts, has low overhead, and is easy to implement. Its performance and accuracy are discussed, in particular with regard to the data to which it is applied. Experience with application to bibliographic and time series data, which may have a dimensionality in the tens of thousands, is described.