  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.
