Network Distance Prediction Based on Decentralized Matrix Factorization

Abstract : Network Coordinate Systems (NCS) are promising techniques to predict unknown network distances from a limited number of measurements. Most NCS algorithms are based on metric space embedding and suffer from the inability to represent distance asymmetries and Triangle Inequality Violations (TIVs). To overcome these drawbacks, we formulate the problem of network distance prediction as guessing the missing elements of a distance matrix and solve it by matrix factorization. A distinct feature of our approach, called Decentralized Matrix Factorization (DMF), is that it is fully decentralized. The factorization of the incomplete distance matrix is collaboratively and iteratively done at all nodes with each node retrieving only a small number of distance measurements. There are no special nodes such as landmarks nor a central node where the distance measurements are collected and stored. We compare DMF with two popular NCS algorithms: Vivaldi and IDES. The former is based on metric space embedding, while the latter is also based on matrix factorization but uses landmarks. Experimental results show that DMF achieves competitive accuracy with the double advantage of having no landmarks and of being able to represent distance asymmetries and TIVs.
Type de document :
Communication dans un congrès
Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.15-26, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_2〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01056303
Contributeur : Hal Ifip <>
Soumis le : lundi 18 août 2014 - 15:54:07
Dernière modification le : vendredi 6 octobre 2017 - 16:12:24
Document(s) archivé(s) le : mardi 11 avril 2017 - 19:44:19

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Yongjun Liao, Pierre Geurts, Guy Leduc. Network Distance Prediction Based on Decentralized Matrix Factorization. Mark Crovella; Laura Marie Feeney; Dan Rubenstein; S. V. Raghavan. 9th International IFIP TC 6 Networking Conference (NETWORKING), May 2010, Chennai, India. Springer, Lecture Notes in Computer Science, LNCS-6091, pp.15-26, 2010, NETWORKING 2010. 〈10.1007/978-3-642-12963-6_2〉. 〈hal-01056303〉

Partager

Métriques

Consultations de la notice

210

Téléchargements de fichiers

179