Improving Table Compression with Combinatorial Optimization

Details Improving Table Compression with Combinatorial Optimization Improving Table Compression with Combinatorial Optimization

2002-03-13

arxiv.org/abs/cs/0203018v1

JACM 50(6):825-851, 2003

Computer Science

Data Structures and Algorithms

22 pages, 2 figures, 5 tables, 23 references. Extended abstract appears in Proc. 13th ACM-SIAM SODA, pp. 213-222, 2002

Scientific paper

We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [SODA'00], in which a table is partitioned by an off-line training procedure into disjoint intervals of columns, each of which is compressed separately by a standard, on-line compressor like gzip. We provide a new theory that unifies previous experimental observations on partitioning and heuristic observations on column permutation, all of which are used to improve compression rates. Based on the theory, we devise the first on-line training algorithms for table compression, which can be applied to individual files, not just continuously operating sources; and also a new, off-line training algorithm, based on a link to the asymmetric traveling salesman problem, which improves on prior work by rearranging columns prior to partitioning. We demonstrate these results experimentally. On various test files, the on-line algorithms provide 35-55% improvement over gzip with negligible slowdown; the off-line reordering provides up to 20% further improvement over partitioning alone. We also show that a variation of the table compression problem is MAX-SNP hard.

Affiliated with

Also associated with

No associations

Rating

Improving Table Compression with Combinatorial Optimization does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Improving Table Compression with Combinatorial Optimization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improving Table Compression with Combinatorial Optimization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-252331