License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2010.172
URN: urn:nbn:de:0030-drops-25959
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2010/2595/
Go to the corresponding LIPIcs Volume Portal

Santos, Jose ; Muggleton, Stephen

Subsumer: A Prolog theta-subsumption engine

pdf-format:
10003.SantosJose.2595.pdf (0.3 MB)

Abstract

State-of-the-art theta-subsumption engines like Django (C) and Resumer2 (Java) are implemented in imperative languages. Since theta-subsumption is inherently a logic problem, in this paper we explore how to efficiently implement it in Prolog.

theta-subsumption is an important problem in computational logic and particularly relevant to the Inductive Logic Programming (ILP) community as it is at the core of the hypotheses coverage test which is often the bottleneck of an ILP system. Also, since most of those systems are implemented in Prolog, they can immediately take advantage of a Prolog based theta-subsumption engine.

We present a relatively simple (~1000 lines in Prolog) but efficient and general theta-subsumption engine, Subsumer. Crucial to Subsumer's performance is the dynamic and recursive decomposition of a clause in sets of independent components. Also important are ideas borrowed from constraint programming that empower Subsumer to efficiently work on clauses with up to several thousand literals and several dozen distinct variables.

Using the notoriously challenging Phase Transition dataset we show that, cputime wise, Subsumer clearly outperforms the Django subsumption engine and is competitive with the more sophisticated, state-of-the-art, Resumer2. Furthermore, Subsumer's memory requirements are only a small fraction of those engines and it can handle arbitrary Prolog clauses whereas Django and Resumer2 can only handle Datalog clauses.

BibTeX - Entry

@InProceedings{santos_et_al:LIPIcs:2010:2595,
  author =	{Jose Santos and Stephen Muggleton},
  title =	{{Subsumer: A Prolog theta-subsumption engine}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{172--181},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Manuel Hermenegildo and Torsten Schaub},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2595},
  URN =		{urn:nbn:de:0030-drops-25959},
  doi =		{10.4230/LIPIcs.ICLP.2010.172},
  annote =	{Keywords: Theta-subsumption, Prolog, Inductive Logic Programming}
}

Keywords: Theta-subsumption, Prolog, Inductive Logic Programming
Collection: Technical Communications of the 26th International Conference on Logic Programming
Issue Date: 2010
Date of publication: 25.06.2010

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI