Compact Lists for Tabled Evaluation

• Type: Article in International Conference Proceedings Book
• Date: 2010

Authors

Joao Raimundo (Author) Other; Ricardo Rocha (Author) FCUP

Conference proceedings International

Title: PRACTICAL ASPECTS OF DECLARATIVE LANGUAGES, PROCEEDINGS

Pages: 249-263

12th International Symposium on Practical Aspects of Declarative Languages

Madrid, SPAIN, JAN 18-19, 2010

Indexing

ISI Web of Knowledge - 1 Citation

Scopus - 1 Citation

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-CBP

DOI: 10.1007/978-3-642-11503-5_21

Abstract (EN): 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, which is regarded as a very compact and efficient; data structure for term representation. Despite these good properties, we found that, for list terms, we can design even more compact and efficient representations. We thus propose a, new representation of list terms for tries that avoids the recursive nature of the WAM representation of list terms in which tries are based. Our experimental results using the YapTab tabling system show a significant reduction in the memory usage for the trie data structures and considerable gains in the running time for storing and loading list terms.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15