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