A Subterm-Based Global Trie for Tabled Evaluation of Logic Programs
João Raimundo and Ricardo Rocha
October 2011
Abstract
Tabling is an implementation technique that overcomes some limitations
of traditional Prolog systems in dealing with redundant
sub-computations and recursion. A critical component in the
implementation of an efficient tabling system is the design of the
table space. The most popular and successful data structure for
representing tables is based on a two-level trie data structure, where
one trie level stores the tabled subgoal calls and the other stores
the computed answers. The Global Trie (GT) is an alternative table
space organization designed with the intent to reduce the tables's
memory usage, namely by storing terms in a global trie, thus
preventing repeated representations of the same term in different trie
data structures. In this paper, we propose an extension to the GT
organization, named Global Trie for Subterms (GT-ST), where compound
subterms in term arguments are represented as unique entries in the
GT. Experimental results using the YapTab tabling system show that
GT-ST support has potential to achieve significant reductions on
memory usage, for programs with increasing compound subterms in term
arguments, without compromising the execution time for other programs.
Bibtex
@InProceedings{raimundo-epia11,
author = {J. Raimundo and R. Rocha},
title = {{A Subterm-Based Global Trie for Tabled Evaluation of Logic Programs}},
booktitle = {Proceedings of the 15th Portuguese Conference on Artificial Intelligence (EPIA 2011)},
pages = {239--253},
number = {7026},
series = {LNAI},
publisher = {Springer},
editor = {L. Antunes and H. S. Pinto},
month = {October},
year = {2011},
address = {Lisboa, Portugal},
}
Download Paper
PDF file
Springer
Download Slides
PDF file