CDoT: Optimizing MAP Queries on Trees

Among the graph structures underlying Probabilistic Graphical Models, trees are valuable tools for modeling several interesting problems, such as linguistic parsing, phylogenetic analysis, and music harmony analysis. In this paper we introduce CDoT, a novel exact algorithm for answering Maximum a Posteriori queries on tree structures. We discuss its properties and study its asymptotic complexity; we also provide an empirical assessment of its performances, showing that the proposed algorithm substantially improves over a dynamic programming based competitor.