Please use this identifier to cite or link to this item: https://doi.org/10.1007/978-3-642-40627-0_53
Title: Optimizing STR algorithms with tuple compression
Authors: Xia, W.
Yap, R.H.C. 
Issue Date: 2013
Citation: Xia, W.,Yap, R.H.C. (2013). Optimizing STR algorithms with tuple compression. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 8124 LNCS : 724-732. ScholarBank@NUS Repository. https://doi.org/10.1007/978-3-642-40627-0_53
Abstract: Table constraints define an arbitrary constraint explicitly as a set of solutions (tuples) or non-solutions. Thus, space is proportional to number of tuples. Simple Tabular Reduction (STR), which dynamically reduces the table size by maintaining a table of only the valid tuples, has been shown to be efficient for enforcing Generalized Arc Consistency. The Cartesian product representation is another way of having a smaller table by compression. We investigate whether STR and the Cartesian product representation can work hand in hand. Our experiments show the compression-based STR can be faster once the tables compress well. Thus, the benefits of the STR2 and STR3 algorithms respectively are retained while consuming less space. © 2013 Springer-Verlag.
Source Title: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
URI: http://scholarbank.nus.edu.sg/handle/10635/78274
ISBN: 9783642406263
ISSN: 03029743
DOI: 10.1007/978-3-642-40627-0_53
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

12
checked on Oct 15, 2018

Page view(s)

31
checked on Aug 10, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.