A Term-Based Global Trie for Tabled Logic Programs
Jorge Costa, João Raimundo and Ricardo Rocha
July 2009
Abstract
A critical component in the implementation of an efficient tabling
system is the design of the data structures and algorithms to access
and manipulate tabled data. Arguably, the most successful data
structure for tabling is tries. However, when used in applications
that pose many queries and/or have a large number of answers, tabling
can build arbitrarily many and/or very large tables, quickly filling
up memory. In this paper, we propose a new design for the table space
organization where all terms in tabled subgoal calls and tabled
answers are represented only once in a common global trie instead of
being spread over several different trie data structures. Our initial
experiments using the YapTab tabling system show significant
reductions on memory usage without compromising running time.
Bibtex
@InProceedings{costa-iclp09,
author = {J. Costa and J. Raimundo and R. Rocha},
title = {{A Term-Based Global Trie for Tabled Logic Programs}},
booktitle = {Proceedings of the 25th International Conference on Logic Programming (ICLP 2009)},
pages = {205--219},
number = {5649},
series = {LNCS},
publisher = {Springer},
editor = {P. Hill and D. S. Warren},
month = {July},
year = {2009},
address = {Pasadena, California, USA},
}
Download Paper
PDF file
Springer
Download Slides
PDF file