作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2015, Vol. 41 ›› Issue (1): 61-64. doi: 10.3969/j.issn.1000-3428.2015.01.011

• 先进计算与数据处理 • 上一篇    下一篇

一种改进的邻接关系可查询压缩算法

高圣巍,彭超   

  1. 华东师范大学软件学院,上海 200062
  • 收稿日期:2014-01-20 修回日期:2014-03-15 出版日期:2015-01-15 发布日期:2015-01-16
  • 作者简介:高圣巍(1989-),男,硕士研究生,主研方向:移动路由算法;彭 超,副教授。
  • 基金资助:
    国家自然科学基金资助项目(91118008,61232006);国家“863”计划基金资助重点项目(SQ2010AA0101016001);上海市教育委员会科研创新基金资助项目(44440590)

An Improved Compression Algorithm Supporting Neighbor Query

GAO Shengwei,PENG Chao   

  1. Software Engineering Institute,East China Normal University,Shanghai 200062,China
  • Received:2014-01-20 Revised:2014-03-15 Online:2015-01-15 Published:2015-01-16

摘要: 目前多数数据压缩算法不能直接在压缩结果上进行数据查询,大数据的线性化压缩算法虽然可直接在压缩后的数据上进行邻接关系查询,但压缩率较低。针对该问题,对线性化压缩的实现原理进行研究,分析MPk线性化算法在不同社会网络样本下的压缩效率,发现线性化压缩结果中存在冗余信息,并针对该情况设计改进算法,删去原有数据结构中的冗余部分,进一步提高压缩率。实验结果证明,改进算法的时间复杂度与原算法相同,压缩率平均提升23%。

关键词: 线性化压缩算法, 大数据, 社会网络, 启发式算法, Eulerian数据结构

Abstract: Nowadays,most data compression algorithms do not support performing query directly on compressed data.Though the compression algorithm can perform query neighbor relations on compressed result,the compression ratio is relatively low.To solve the problem,this paper does some research on the principle of linearization compression algorithm.It analyzes the compression ratio of MPk algorithm in different sample social network and finds the redundant information in compressed result.To eliminate these redundant information,it improves the original data structure,removes the unnecessary bits and improves the compression ratio.Experiments show that the proposed algorithm has same time complexity compared with primal algorithm,but the compression ratio can be increased by 23% in average.

Key words: linearization compression algorithm, big data, social network, heuristic algorithm, Eulerian data structure

中图分类号: