loading...
Improving Hybrid MDS with Pivot-Based Searching
Seattle, Washington October 20-October 21
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/INFVIS.2003.12490122003 IEEE Symposium on Information Vi ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Alistair Morrison, University of Glasgow, United Kingdom
Matthew Chalmers, University of Glasgow, United Kingdom
An algorithm is presented for the visualisation of multidimensional abstract data, building on a hybrid model introduced at InfoVis 2002. The most computationally complex stage of the original model involved performing a nearest-neighbour search for every data item. 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 pivot items. In improving this computational bottleneck, the complexity is reduced from O(N\sqrt N) to O (N^{\frac{5} {4}} ). As well as documenting this improvement, the paper describes evaluation with a data set of 108000 14-dimensional items; a considerable increases on the size of data previously tested. 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.
Index Terms:
Multidimensional scaling, MDS, spring models, hybrid algorithms, pivots, near-neighbour search, force directed placement
Citation:
Alistair Morrison, Matthew Chalmers, "Improving Hybrid MDS with Pivot-Based Searching," infovis, pp.11, 2003 IEEE Symposium on Information Visualization (InfoVis 2003), 2003
Usage of this product signifies your acceptance of the Terms of Use.