压缩数据上的关系代数操作算法

来源：计算机应用杂志2016年第1期北京时间：

作者：丁鑫哲, 张兆功, 李建中, 谭龙, 刘勇

单位：1. 黑龙江大学 计算机科学技术学院, 哈尔滨 150080;2. 哈尔滨工业大学 计算机科学技术学院, 哈尔滨 150010

摘要：针对在大数据管理中,在压缩的数据上无需解压即可进行相关操作的问题,在数据服从正态分布的前提下,根据列数据存储的特点,提出了一种新的面向列存储的压缩方法——CCA。首先,通过对列数据的长度进行归类;然后,采用抽样的方法获得重复度较高的前缀;最后,使用字典编码进行压缩,提出了列索引(CI)和列实体(CR)作为数据压缩结构来降低大数据存储的空间需求,从而直接有效地在压缩数据上支持选择、投影、连接等基本操作,并实现了基于CCA的数据库原型系统——D-DBMS。理论分析和在1 TB数据上的实验结果表明,该压缩算法能够显著提高大数据的存储效率和数据操作性能,与BAP和TIDC压缩方法相比,在压缩率分别提高了51%、14%;在执行速度上提高了47%、42%。

关键词：大数据压缩,列索引,列实体,关系代数操作

基金资助：国家自然科学基金资助项目(81273649);黑龙江省自然科学基金资助项目(F201434)。