Preventing Unnecessary Groundings in the Lifted Dynamic Junction Tree Algorithm

2018/07/02 by Marcel Gehrke, Tanya Braun, Gehrke, Marcel +3
Computer Science · #Data Management and Algorithms #Advanced Database Systems and Queries #Bayesian Modeling and Causal Inference

paper · pdf · doi:10.48550/arxiv.1807.00744

Abstract

The lifted dynamic junction tree algorithm (LDJT) efficiently answers filtering and prediction queries for probabilistic relational temporal models by building and then reusing a first-order cluster representation of a knowledge base for multiple queries and time steps. Unfortunately, a non-ideal elimination order can lead to groundings even though a lifted run is possible for a model. We extend LDJT (i) to identify unnecessary groundings while proceeding in time and (ii) to prevent groundings by delaying eliminations through changes in a temporal first-order cluster representation. The extended version of LDJT answers multiple temporal queries orders of magnitude faster than the original version.

Related

• Answering Hindsight Queries with Lifted Dynamic Junction Trees
• Fusing First-order Knowledge Compilation and the Lifted Junction Tree\n Algorithm
• On the Completeness and Complexity of the Lifted Dynamic Junction Tree\n Algorithm
• Taming Reasoning in Temporal Probabilistic Relational Models
• Temporal Knowledge Base Completion: New Algorithms and Evaluation Protocols