Skip to Main content Skip to Navigation
Conference papers

Distributed tree decomposition with privacy

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00790112
Contributor : Philippe Dague Connect in order to contact the contributor
Submitted on : Tuesday, February 19, 2013 - 2:24:45 PM
Last modification on : Sunday, June 26, 2022 - 11:58:18 AM
Long-term archiving on: : Monday, May 20, 2013 - 4:02:06 AM

File

main-token.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00790112, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

63

Files downloads

526