Improving table compression with combinatorial optimization
Improving table compression with combinatorial optimization
复制标题
DOI：
10.1145/950620.950622
复制
发表时间：
2003-11-01
影响因子：
2.5
通讯作者：
Giancarlo, R
中科院分区：
文献类型：
--
作者：
Buchsbaum, AL;Fowler, GS;Giancarlo, R
我们研究了在Buchsbaum等人[2000]引入的分区训练范例中压缩大规模表的问题，其中表通过离线训练过程分区为不相交的列间隔，每个列间隔分别由标准的在线压缩器（如gzip）压缩。我们提供了一个新的理论，统一以前的实验观察分区和启发式观察列排列，所有这些都被用来提高压缩率。基于这一理论，我们设计了第一个在线训练算法表压缩，它可以应用于单个文件，而不仅仅是连续操作的源;也是一个新的，离线训练算法，基于链接的不对称旅行商问题，它改善了以前的工作，通过重新排列列分区之前。我们证明了这些结果的实验。在各种测试文件上，在线算法比gzip提供了35-55%的改进，速度可以忽略不计;离线重新排序比单独分区提供了高达20%的进一步改进。我们还表明，表压缩问题的变化是MAX-SNP硬。
We study the problem of compressing massive tables within the partition-training paradigm introduced by Buchsbaum et al. [2000], 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 this 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.