检索结果-内蒙古大学图书馆

A Universal Parallel two-pass MDL Context Tree Compression Algorithm

IEEE JOURNAL OF SELECTED TOPICS IN SIGNAL PROCESSING 2015年第4期9卷 741-748页

作者： Krishnan, Nikhil Baron, Dror N Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

Computing problems that handle large amounts of data necessitate the use of lossless data compression for efficient storage and transmission. We present a novel lossless universal data compression algorithm that uses parallel computational units to increase the throughput. The length-N input sequence is partitioned into B blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of B but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) context tree source underlying the entire input, and then encode each of the B blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i. e., its computational complexity is O(N/B) Its redundancy is approximately B log (N/B) bits above Rissanen's lower bound on universal compression performance, with respect to any context tree source whose maximal depth is at most log (N/B). We improve the compression by using different quantizers for states of the context tree based on the number of symbols corresponding to those states. Numerical results from a prototype implementation suggest that our algorithm offers a better trade-off between compression and throughput than competing universal data compression algorithms.

关键词： Big data computational complexity data compression distributed computing minimum description length parallel algorithms redundancy two-pass code universal compression work-efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

Performance of Parallel two-pass MDL Context Tree Algorithm

Performance of Parallel Two-Pass MDL Context Tree Algorithm

引用

IEEE Global Conference on Signal and Information Processing (GlobalSIP)

作者： Krishnan, Nikhil Baron, Dror North Carolina State Univ Dept Elect & Comp Engn Raleigh NC 27695 USA

ISBN: (纸本)9781479970889

Computing problems that handle large amounts of data necessitate the use of lossless data compression for efficient storage and transmission. We present numerical results that showcase the advantages of a novel lossless universal data compression algorithm that uses parallel computational units to increase the throughput with minimal degradation in the compression quality. Our approach is to divide the data into blocks, estimate the minimum description length (MDL) context tree source underlying the entire input, and compress each block in parallel based on the MDL source. Numerical results from a prototype implementation suggest that our algorithm offers a better trade-off between compression and throughput than competing universal data compression algorithms.

关键词： big data distributed computing minimum description length parallel algorithms redundancy two-pass code universal data compression

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：