Scalable Anti-KNN: Decentralized Computation of k-Furthest-Neighbor Graphs with HyFN

Abstract : The decentralized construction of k-Furthest-Neighbor graphs has been little studied, although such structures can play a very useful role, for instance in a number of distributed resource allocation problems. In this paper we define KFN graphs; we propose HyFN, a generic peer-to-peer KFN construction algorithm, and thoroughly evaluate its behavior on a number of logical networks of varying sizes. 1 Motivation k-Nearest-Neighbor (KNN) graphs have found usage in a number of domains, including machine learning, recommenders, and search. Some applications do not however require the k closest nodes, but the k most dissimilar nodes, what we term the k-Furthest-Neighbor (KFN) graph. Virtual Machines (VMs) placement —i.e. the (re-)assignment of workloads in virtualised IT environments— is a good example of where KFN can be applied. The problem consists in finding an assignment of VMs on physical machines (PMs) that minimises some cost function(s) [27]. The problem has been described as one of the most complex and important for the IT industry [3], with large potential savings [20]. An important challenge is that a solution does not only consist in packing VMs onto PMs — it also requires to limit the amount of interferences between VMs hosted on the same PM [31]. Whatever technique is used (e.g. clustering [21]), interference aware VM placement algorithms need to identify complementary workloads — i.e. workloads that are dissimilar enough that the interferences between them are minimised. This is why the application of KFN graphs would make a lot of sense: identifying quickly complementary workloads (using KFN) to help placement algorithms would decrease the risks of interferences. The construction of KNN graphs in decentralized systems has been widely studied in the past [17, 30, 4, 14]. However, existing approaches typically assume a form of " likely transitivity " of similarity between nodes: if A is close to B, and B to C, then A is likely to be close to C. Unfortunately this property no longer holds when constructing KFN graphs. As a result, these approaches, as demonstrated in the remainder of the paper, are not working anymore when applied to this new problem.
Type de document :
Communication dans un congrès
Lydia Y. Chen; Hans Reiser. DAIS 2017 - 17th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems, Jun 2017, Neuchâtel, Switzerland. Springer, pp.101-114, 2017, 〈10.1007/978-3-319-59665-5_7〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01617211
Contributeur : François Taïani <>
Soumis le : lundi 16 octobre 2017 - 13:36:42
Dernière modification le : jeudi 12 avril 2018 - 01:54:52
Document(s) archivé(s) le : mercredi 17 janvier 2018 - 13:53:13

Fichier

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

Identifiants

Citation

Simon Bouget, David Bromberg, François Taïani, Anthony Ventresque. Scalable Anti-KNN: Decentralized Computation of k-Furthest-Neighbor Graphs with HyFN. Lydia Y. Chen; Hans Reiser. DAIS 2017 - 17th IFIP WG 6.1 International Conference on Distributed Applications and Interoperable Systems, Jun 2017, Neuchâtel, Switzerland. Springer, pp.101-114, 2017, 〈10.1007/978-3-319-59665-5_7〉. 〈hal-01617211〉

Partager

Métriques

Consultations de la notice

255

Téléchargements de fichiers

29