loading...
Table Compression by Record Intersections
March 25-March 27
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DCC.2008.105Data Compression Conference (dcc 2008)
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Saturated patterns with don’t care like those emerged in biosequence motif discovery haveproven a valuable notion also in the design of lossless and lossy compression of sequence data. In independent endeavors, the peculiarities inherent to the compression of tables have been examined, leading to compression schemata advantageously hinged on a prudent rearrangement of columns. The present paper introduces off-line table compression by textual substitution in which the patterns used in compression are chosen among models or templates that capture recurrent record subfields. A model record is to be interpreted here as a sequence of intermixed solid and don’t care characters that obeys, in addition, some conditions of saturation: most notably, it must be not possible to replace a don’t care in the model by a solid character without having to forfeit some of its occurrences in the table. Saturation is expected to save on the size of the codebook at the outset, and hence to improve compression. It also induces some clustering of the records in the table, which may present independent interest. Results from preliminary experiments show the savings and potential for classification brought about by this method in connection with a table of specimens collected in a context of biodiversity studies.
Index Terms:
table compression, saturated record, intrecord
Citation:
Alberto Apostolico, Fabio Cunial, Vineith Kaul, "Table Compression by Record Intersections," dcc, pp.13-22, Data Compression Conference (dcc 2008), 2008
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions