Distributed tree decomposition with privacy - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

Distributed tree decomposition with privacy

Vincent Armant
Laurent Simon
  • Fonction : Auteur
  • PersonId : 830497
Philippe Dague

Résumé

Tree Decomposition of Graphical Models is a well known method for mapping a graph into a tree, that is commonly used to speed up solving many problems. However, in a distributed case, one may have to respect the privacy rules (a subset of variables may have to be kept secret in a peer), and the initial network architecture (no link can be dynamically added). In this context, we propose a new distributed method, based on token passing and local elections, that shows performances (in the jointree quality) close to the state of the art Bucket Elimination in a centralized case (i.e. when used without these two restrictions). Until now, the state of the art in a distributed context was using a Depth-First traversal with a clever heuristic. It is outperformed by our method on two families of problems sharing the small-world property.
Fichier principal
Vignette du fichier
main-token.pdf (433.59 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00790112 , version 1 (19-02-2013)

Identifiants

  • HAL Id : hal-00790112 , version 1

Citer

Vincent Armant, Laurent Simon, Philippe Dague. Distributed tree decomposition with privacy. CP - 18th International Conference on Principles and Practice of Constraint Programming, Oct 2012, Québec, Canada. ⟨hal-00790112⟩
68 Consultations
558 Téléchargements

Partager

Gmail Facebook X LinkedIn More