Tabling Logic Programs in a Common Global Trie

Jorge Costa and Ricardo Rocha

December 2008


Abstract

The performance of tabled evaluation largely depends on the implementation of the table space. Arguably, the most successful data structure for tabling is tries. However, while tries are efficient for variant based tabled evaluation, they are limited in their ability to recognize and represent repeated answers for different calls. In this paper, we propose a new design for the table space where terms in a tabled subgoal call or/and answer are stored in a common global trie instead of being spread over several different tries. Our preliminary experiments using the YapTab tabling system show very promising reductions on memory usage.

Bibtex

@InProceedings{costa-ciclops08,
  author =    {J. Costa and R. Rocha},
  title =     {{Tabling Logic Programs in a Common Global Trie}},
  booktitle = {Proceedings of the 8th Colloquium on Implementation of Constraint and LOgic Programming 
               Systems (CICLOPS 2008)},
  pages =     {48--59},
  editor =    {M. Carro and B. Demoen},
  month =     {December},
  year =      {2008},
  address =   {Udine, Italy},
}

Download Paper

PDF file

Download Slides

PDF file