Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm

Tanya Braun, Ralf Möller

Abstract

Standard approaches for inference in probabilistic formalisms with first-order constructs include lifted variable elimination (LVE) for single queries. To handle multiple queries efficiently, the lifted junction tree algorithm (LJT) uses a first-order cluster representation of a knowledge base and LVE in its computations. We extend LJT with a full formal specification of its algorithm steps incorporating (i) the lifting tool of counting and (ii) answering of conjunctive queries. Given multiple queries, e.g., in machine learning applications, our approach enables us to compute answers faster than the current LJT and existing approaches tailored for single queries.
Original languageEnglish
Title of host publicationGraph Structures for Knowledge Representation and Reasoning
EditorsMadalina Croitoru, Pierre Marquis, Sebastian Rudolph, Gem Stapleton
Number of pages19
Volume10775
Place of PublicationCham
PublisherSpringer International Publishing
Publication date21.03.2018
Pages54-72
ISBN (Print)978-3-319-78101-3
ISBN (Electronic)978-3-319-78102-0
DOIs
Publication statusPublished - 21.03.2018
Event5th International Workshop on Graph Structures for Knowledge Representation and Reasoning - Melbourne, Australia
Duration: 21.08.201721.08.2017
Conference number: 212419

DFG Research Classification Scheme

  • 4.43-01 Theoretical Computer Science

Fingerprint

Dive into the research topics of 'Counting and Conjunctive Queries in the Lifted Junction Tree Algorithm'. Together they form a unique fingerprint.

Cite this