Efficient tabling of structured data with enhanced hash-consing

Neng-Fa Zhou, Christian Theil Have

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

Resumé

Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called input sharing and hash code memoization, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.
OriginalsprogEngelsk
TidsskriftTheory and Practice of Logic Programming
Vol/bind12
Udgave nummer4-5
Sider (fra-til)547-563
Antal sider16
ISSN1471-0684
DOI
StatusUdgivet - 1 jul. 2012

Citer dette

Zhou, Neng-Fa ; Have, Christian Theil. / Efficient tabling of structured data with enhanced hash-consing. I: Theory and Practice of Logic Programming. 2012 ; Bind 12, Nr. 4-5. s. 547-563.
@inproceedings{f3c8a137d7d24809ae8bee37b95f4002,
title = "Efficient tabling of structured data with enhanced hash-consing",
abstract = "Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called input sharing and hash code memoization, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.",
author = "Neng-Fa Zhou and Have, {Christian Theil}",
year = "2012",
month = "7",
day = "1",
doi = "10.1017/S1471068412000178",
language = "English",
volume = "12",
pages = "547--563",
journal = "Theory and Practice of Logic Programming",
issn = "1471-0684",
publisher = "Cambridge University Press",
number = "4-5",

}

Efficient tabling of structured data with enhanced hash-consing. / Zhou, Neng-Fa; Have, Christian Theil.

I: Theory and Practice of Logic Programming, Bind 12, Nr. 4-5, 01.07.2012, s. 547-563.

Publikation: Bidrag til tidsskriftKonferenceartikelForskningpeer review

TY - GEN

T1 - Efficient tabling of structured data with enhanced hash-consing

AU - Zhou, Neng-Fa

AU - Have, Christian Theil

PY - 2012/7/1

Y1 - 2012/7/1

N2 - Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called input sharing and hash code memoization, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.

AB - Current tabling systems suffer from an increase in space complexity, time complexity or both when dealing with sequences due to the use of data structures for tabled subgoals and answers and the need to copy terms into and from the table area. This symptom can be seen in not only B-Prolog, which uses hash tables, but also systems that use tries such as XSB and YAP. In this paper, we apply hash-consing to tabling structured data in B-Prolog. While hash-consing can reduce the space consumption when sharing is effective, it does not change the time complexity. We enhance hash-consing with two techniques, called input sharing and hash code memoization, for reducing the time complexity by avoiding computing hash codes for certain terms. The improved system is able to eliminate the extra linear factor in the old system for processing sequences, thus significantly enhancing the scalability of applications such as language parsing and bio-sequence analysis applications. We confirm this improvement with experimental results.

U2 - 10.1017/S1471068412000178

DO - 10.1017/S1471068412000178

M3 - Conference article

VL - 12

SP - 547

EP - 563

JO - Theory and Practice of Logic Programming

JF - Theory and Practice of Logic Programming

SN - 1471-0684

IS - 4-5

ER -