Download   View accepted manuscript: A LinearSpace Algorithm for Distance Preserving Graph Embedding (PDF, 761 KB)


Author  Search for: Asano, T.; Search for: Bose, P.; Search for: Carmi, P.; Search for: Maheshwari, A.; Search for: Shu, Chang; Search for: Smid, M.; Search for: Wuhrer, Stefanie 

Type  Article 

Conference  Computational Geometry: Theory and Applications. 

Volume  42(4) 

Abstract  The distance preserving graph embedding problem is to embed the vertices of a given weighted graph onto points in ddimensional Euclidean space for a constant d such that for each edge the distance between their corresponding endpoints is as close to the weight of the edge as possible. If the given graph is complete, that is, if the weights are given as a full matrix, then multidimensional scaling [13] can minimize the sum of squared embedding errors in quadratic time. A serious disadvantage of this approach is its quadratic space requirement. In this paper we develop a linearspace algorithm for this problem for the case when the weight of any edge can be computed in constant time. A key idea is to partition a set of n objects into O(?n) disjoint subsets (clusters) of size O(?n) such that the minimum inter cluster distance is maximized among all possible such partitions. Experimental results are included comparing the performance of the newly developed approach to the performance of the wellestablished leastsquares multidimensional scaling approach [13] using three different applications. Although leastsquares multidimensional scaling gave slightly more accurate results than our newly developed approach, leastsquares multidimensional scaling ran out of memory for data sets larger than 15000 vertices. 

Publication date  2008 

Language  English 

Affiliation  NRC Institute for Information Technology; National Research Council Canada 

Peer reviewed  No 

NRC number  50403 

NPARC number  8913549 

Export citation  Export as RIS 

Report a correction  Report a correction 

Record identifier  f72c33358c524d9688d6ab8837810ddd 

Record created  20090422 

Record modified  20160509 

Bookmark and share  
