{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:20:35Z","timestamp":1777778435508,"version":"3.51.4"},"reference-count":36,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2004,6,1]],"date-time":"2004-06-01T00:00:00Z","timestamp":1086048000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information Visualization"],"published-print":{"date-parts":[[2004,6]]},"abstract":"<jats:p>\n                    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 bottle-neck, the algorithmic complexity is reduced from O( N\u221aN) to O( N\n                    <jats:sup>5\/4<\/jats:sup>\n                    ). 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.\n                  <\/jats:p>","DOI":"10.1057\/palgrave.ivs.9500069","type":"journal-article","created":{"date-parts":[[2004,5,20]],"date-time":"2004-05-20T05:07:02Z","timestamp":1085029622000},"page":"109-122","source":"Crossref","is-referenced-by-count":19,"title":["A Pivot-Based Routine for Improved Parent-Finding in Hybrid MDS"],"prefix":"10.1177","volume":"3","author":[{"given":"Alistair","family":"Morrison","sequence":"first","affiliation":[{"name":"Department of Computing Science, University of Glasgow, Glasgow, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthew","family":"Chalmers","sequence":"additional","affiliation":[{"name":"Department of Computing Science, University of Glasgow, Glasgow, U.K."}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2004,6,1]]},"reference":[{"key":"bibr1-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1109\/INFVIS.2003.1249012"},{"key":"bibr2-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1057\/PALGRAVE.IVS.9500023"},{"key":"bibr3-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1145\/365024.365097"},{"key":"bibr4-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Amenta N, Klinger J. Visualizing sets of evolutionary trees. Proceedings of the IEEE Symposium on Information Visualization 2002, IEEE, IEEE Computer Society: New York, 2002; 71\u201374.","DOI":"10.1109\/INFVIS.2002.1173150"},{"key":"bibr5-palgrave.ivs.9500069","unstructured":"Koren Y, Carmel L, Harel D. ACE: a fast multiscale eigenvectors computation for drawing huge graphs. Proceedings of the IEEE Symposium on Information Visualization 2002, IEEE Computer Society: New York, 2002; 137\u2013144."},{"key":"bibr6-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380211102"},{"key":"bibr7-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1109\/VISUAL.1996.567787"},{"key":"bibr8-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Morrison A, Ross G, Chalmers M. A hybrid layout algorithm for subquadratic multidimensional scaling. Proceedings of the IEEE Symposium on Information Visualization 2002, IEEE, IEEE Computer Society: New York, 2002; 152\u2013158.","DOI":"10.1109\/INFVIS.2002.1173161"},{"key":"bibr9-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.ivs.9500040"},{"key":"bibr10-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF00275687"},{"key":"bibr11-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2711-1"},{"key":"bibr12-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF02288916"},{"key":"bibr13-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289630"},{"key":"bibr14-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289565"},{"key":"bibr15-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF02310791"},{"key":"bibr16-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.4135\/9781412985130"},{"key":"bibr17-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Frick A, Ludwig A, Mehldau H. A fast adaptive layout algorithm for undirected graphs. In: Tamassia R, Tollis IG (Eds). Proceedings of the DIMACS Int. Work. Graph Drawing GD, Berlin, Germany: Springer-Verlag, 1994; 388\u2013403.","DOI":"10.1007\/3-540-58950-3_393"},{"key":"bibr18-palgrave.ivs.9500069","first-page":"149","volume":"42","author":"Eades P.","year":"1984","journal-title":"Congressus Numerantium"},{"key":"bibr19-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Ross G, Chalmers M. A visual workspace for hybrid multidimensional scaling algorithms. Proceedings of the IEEE Symposium on Information Visualization 2003, IEEE Computer Society: New York, 2003; 91\u201396.","DOI":"10.1109\/INFVIS.2003.1249013"},{"key":"bibr20-palgrave.ivs.9500069","unstructured":"Gionis A, Indyk P, Motwani R. Similarity search in high dimensions via hashing. Proceedings of 25th International Conference on Very Large Data Bases 1999; 518\u2013529."},{"key":"bibr21-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502808"},{"key":"bibr22-palgrave.ivs.9500069","unstructured":"Brin S. Near neighbor search in large metric spaces. Proceedings of the 21st Conference on Very Large Databases 1995; 574\u2013584."},{"key":"bibr23-palgrave.ivs.9500069","unstructured":"Ciaccia P, Patella M, Zezula P. M-tree: an efficient access method for similarity search in metric spaces. Proceedings of the 23rd Conference on Very Large Data Bases 1997; 426\u2013435."},{"key":"bibr24-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1145\/116873.116880"},{"key":"bibr25-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1145\/362003.362025"},{"key":"bibr26-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(86)90013-9"},{"key":"bibr27-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1007\/BF02776078"},{"key":"bibr28-palgrave.ivs.9500069","volume-title":"Perceptrons","author":"Minsky M","year":"1969"},{"key":"bibr29-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"bibr30-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Maneewongvatana S, Mount DM. On the efficiency of nearest neighbor searching with data clustered in lower dimensions. International Conference on Computational Science 2001; 842\u2013851.","DOI":"10.1007\/3-540-45545-0_96"},{"key":"bibr31-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011343115154"},{"key":"bibr32-palgrave.ivs.9500069","doi-asserted-by":"crossref","unstructured":"Baillie M, Jose JM. Audio-based event detection for sports video. Proceedings of the International Conference of Image and Video Retrieval, Springer: Berlin, 2003.","DOI":"10.1007\/3-540-45113-7_30"},{"key":"bibr33-palgrave.ivs.9500069","volume-title":"Fundamentals of Speech Recognition","author":"Rabiner L","year":"1993"},{"key":"bibr34-palgrave.ivs.9500069","unstructured":"MacQueen J. Some methods for classification and analysis of multivariate observations. Proceedings of the Fifth Berkeley Symposium on Mathematics and Probability, University of California Press: Berkeley, 1967; 281\u2013297."},{"key":"bibr35-palgrave.ivs.9500069","volume-title":"Combining and comparing clustering and layout algorithms","author":"Morrison A","year":"2002"},{"key":"bibr36-palgrave.ivs.9500069","doi-asserted-by":"publisher","DOI":"10.1057\/palgrave.ivs.9500056"}],"container-title":["Information Visualization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1057\/palgrave.ivs.9500069","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1057\/palgrave.ivs.9500069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:19:30Z","timestamp":1777490370000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1057\/palgrave.ivs.9500069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,6]]},"references-count":36,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2004,6]]}},"alternative-id":["10.1057\/palgrave.ivs.9500069"],"URL":"https:\/\/doi.org\/10.1057\/palgrave.ivs.9500069","relation":{},"ISSN":["1473-8716","1473-8724"],"issn-type":[{"value":"1473-8716","type":"print"},{"value":"1473-8724","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,6]]}}}