图数据表示与压缩技术综述


软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn Journal of Software,2014,25(9):1937−1952 [doi: 10.13328/j.cnki.jos.004636] http://www.jos.org.cn ©中国科学院软件研究所版权所有. Tel/Fax: +86-10-62562563 图数据表示与压缩技术综述∗ 张 宇 1,2, 刘燕兵 1, 熊 刚 1, 贾 焰 3, 刘 萍 1, 郭 莉 1 1(中国科学院 信息工程研究所,北京 100093) 2(中国科学院大学,北京 100049) 3(国防科学技术大学 计算机学院,湖南 长沙 410073) 通信作者: 熊刚, E-mail: xionggang@iie.ac.cn 摘 要: 对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩 ,是大规模图数据分析处理的基础 .图数据 压缩技术可以有效地降低图数据的存储空间,同时支持在压缩形式的图数据上进行快速访问 .通过深入分析该技术 的发展现状,将该技术分为基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术、面向特定查询 的图压缩技术 4 类.分别对每类技术详细分析了其代表方法并比较了它们之间的性能差异.最后对该技术进行了总 结和展望. 关键词: 图数据管理;空间缩减;图数据压缩;网页图;社交网络 中图法分类号: TP311 中文引用格式: 张宇,刘燕兵,熊刚,贾焰,刘萍,郭莉.图数据表示与压缩技术综述.软件学报,2014,25(9):1937−1952. http://www. jos.org.cn/1000-9825/4636.htm 英文引用格式: Zhang Y, Liu YB, Xiong G, Jia Y, Liu P, Guo L. Survey on succinct representation of graph data. Ruan Jian Xue Bao/Journal of Software, 2014,25(9):1937−1952 (in Chinese). http://www.jos.org.cn/1000-9825/4636.htm Survey on Succinct Representation of Graph Data ZHANG Yu1,2, LIU Yan-Bing1, XIONG Gang1, JIA Yan3, LIU Ping1, GUO Li1 1(Institute of Information Engineering, The Chinese Academy of Sciences, Beijing 100093, China) 2(University of Chinese Academy of Sciences, Beijing 100049, China) 3(School of Computer Science, National University of Defense Technology, Changsha 410073, China) Corresponding author: XIONG Gang, E-mail: xionggang@iie.ac.cn Abstract: How to effectively compress and represent the large-scale graphic data becomes the fundamental issue for analysis and processing. Graphic data compression technology is an effective solution to significantly reduce the storage space while supporting fast access in the compressed form. An in-depth analysis is provided on the current development of the technologies, including compression technology based on the traditional storage structure, Web graph compression technology, social network compression technology and compression technology for a particular query. A detailed analysis and performance comparison about the representative methods of each technology is presented. Finally, the summary and prospect are listed. Key words: graph data management; space reduction; graph data compression; Web graph; social network 随着移动互联网、物联网等技术的发展,众多新兴应用以前所未有的方式和速度产生并积累着大量数据, 如何对这些数据进行分析并使用,已经成为许多领域面临的机遇与挑战,大数据(big data)时代已经到来.2010 年 国际超级计算大会(Supercomputing Conference)为评估超级计算机对大数据的处理性能,定义了新的排名方法 Graph500[1],比较超级计算机在图数据(graph data)上的处理能力.在大数据分析的过程中,图作为一种有效描述 ∗ 基金项目: 国家自然科学基金(61202477); 国家科技支撑计划(2012BAH46B02); 中国科学院战略性科技先导专项(XDA060 30602) 收稿时间: 2014-01-26; 修改时间: 2014-04-29, 2014-06-09; 定稿时间: 2014-07-05 1938 Journal of Software 软件学报 Vol.25, No.9, September 2014 大数据的数据结构,扮演着越来越重要的角色,在互联网分析[2]、社交网络分析[3]、推荐网络分析[4]等领域,许多 计算问题都可以转化为一个基于图的问题,并且使用图上的相关算法来解决.在大规模图数据分析处理应用中, 对包含亿万个节点和边的图数据进行高效、紧凑的表示和压缩,是当前的研究热点之一. 在互联网分析中,将每一个页面对应图上的一个节点,将两个页面之间的链接对应图上的一条有向边,从而 将互联网转换为一个有向的网页图(Web graph),通过对网页图的分析进行网页的排序.搜索引擎中使用的两种 经典的网页排序算法 Pagerank[5]和 HITS[6],都是基于计算图上节点的出度和入度以及节点之间的连接关系等 基本操作.在社交网络(social network)分析中,将社交网络中的实体和他们之间的关系转化为相应的图数据.在 社交网络图的基础上,可以对社交网络进行相关研究,包括社区发现和重要角色检测[7,8],以及信息传播模式分 析[9−11]等.文献[12]提出的垃圾邮件检测方法可以归结为寻找强连通分量、集团枚举和计算最小割等基于图的 问题.一些常见的网络挖掘算法,比如网络结构和演化过程的发现都是根据基于图的深度优先搜索、宽度优先 搜索、可达性、强连通性和弱连通性等基本算法和性质[13]. 为了高效地支持图数据上的基本算法和操作,需要设计一种数据结构来存储这个图,并且可以快速地做一 些图上的基本操作,比如查询给定的一个节点的所有邻居或者判断两个节点之间是否联通等.传统的存储方法 是采用关联矩阵或者邻接表,为了支持快速的查询,通常将整个关联矩阵或邻接表加载到内存中.但是在实际应 用中,这样的方法会面临存储空间过大的问题.以社交网络为例,根据 GlobalWebIndex[14]统计,2013 年 Facebook 用户量已经超过 11 亿,平均每个人的好友超过 100 位,使用邻接表来存储所有用户的关系信息,需要接近 1TB 的存储空间;以互联网为例,根据中国互联网络信息中心(CNNIC)发布的《第 29 次中国互联网络发展状况统计 报告》[15],中国网页数量为 866 亿个,超链接数量据估计超过 1012,使用邻接表来存储网页直接的链接关系信息 需要超过 16TB 的存储空间.同时随着用户量和信息量的快速增长,存储问题也只会变得越来越严峻. 针对大规模图数据存储空间过大的问题,当前主要从3 个方面进行研究:(1) 硬盘的存储价格相对于内存是 非常便宜的,可以使用外存储器存储图数据[16,17],但是由于硬盘的访问速度比内存访问速度慢 4~6 个数量级,导 致查询产生较大的延时.可以通过优化图数据处理时的访问局部性,以减少磁盘的 I/O 次数,达到降低访问延时 的目的.该技术适用于访问局部性较好的图数据.(2) 使用分布式系统是解决大规模数据的有效方法[18−20],将图 数据分割为多个部分,分别存储在分布式系统中不同的计算机内存中,但是由于图数据的耦合性较强,导致分布 式系统的通信代价较高,会使查询产生较大的延时.可以通过设计较好的图分割算法,使得分割后的不同子图规 模均等并且子图之间的连通性较低,以降低通信代价,较少延时.该技术适用于易于分割的图数据.(3) 将图数据 转换为占用空间较小的压缩形式存放在内存中[21,22],同时可以支持查询,查询的时间增长为数倍于不压缩的形 式,但是延时远小于前两种方案.该技术适用于访问局部性较差或者耦合性较强不易分割的图数据. 对于上述 3 种解决大规模图数据存储空间过大的方法,本文主要讨论第 3 种,在保证查询时间的前提下压 缩存储空间.虽然这种方法并不能解决所有的问题,有些规模特别大的图数据可能压缩后依然不能全部放到内 存中,但是也可以通过压缩存储空间来改善另外两种方法的性能.对于硬盘存储的数据结构,如果可以在保持访 问局部性的前提下压缩存储空间,那么就可以减少硬盘读取次数,以提高访问速度.对于分布式系统,压缩存储 空间可以使用更少的处理节点来完成相同的任务,同时也可以减少处理节点之间的通信代价.因此,对图数据压 缩技术的研究是一项非常有意义的工作. 本文第 1 节主要给出图数据压缩技术的问题描述、相关定义以及当前面临的主要问题.第 2 节~第 5 节依 次介绍 4 种压缩技术,分别是基于传统存储结构的压缩技术、网页图压缩技术、社交网络图压缩技术和面向特 定查询的图压缩技术.第 6 节总结全文并指出一些未来的研究方向. 1 问题描述 1.1 图的基本概念与定义 本文中使用 G=(V,E)表示一个图,其中 V 表示图中节点集合、E 表示图中边集合.使用 n(n=|V|)表示节点的 个数,m(m=|E|)表示边的个数.图数据通常采用关联矩阵(adjacency matrix)和邻接表(adjacency list)作为存储结 张宇 等:图数据表示与压缩技术综述 1939 构.按照图中的边是否有方向,图可分为有向图和无向图,图 1(a)为一个有向图的拓扑结构,图 1(b)和图 1(c)分别 为该图对应的关联矩阵和邻接表,表 1 给出了有向图和无向图分别采用关联矩阵和邻接表两种存储结构所需 要的存储空间复杂度.本文中将所有图都看作是有向图,图中的边都看作有向边,因为无向图中的无向边可以转 化为这条边对应的两个节点之间的两条有向边.对于节点 v∈V,u∈V 使用 e(v,u)∈E 表示图中 v 指向 u 的一条边. 使用 out(v)表示节点 v 指向的所有节点的集合,out(v)={v|v∈V,e(v,u)∈E},即节点 v 的外邻(out-neighbor).使用 in(v) 表示指向节点 v 的所有节点的集合,in(v)={v|v∈V,e(u,v)∈E},即节点 v 的内邻(in-neighbor). Fig.1 A directed graph and its adjacency matrix and adjacency list structure 图 1 有向图和其对应的关联矩阵与邻接表 Table 1 Comparison of directed and undirected graph space complexity using adjacency matrix and list matrix 表 1 有向图和无向图分别使用关联矩阵和邻接表时的空间复杂度对比 有向图 无向图 关联矩阵 O(n2) O(n(n−1)/2) 邻接表 O(n+m) O(n+m) 从表 1 中可以看出,这两种存储结构的存储代价非常高昂,前面提到的随着社交网络等数据规模的不断增 加,存储空间过大问题表现得越来越严重.但是在实际应用中,图数据只需提供几种特定的查询就可以满足需 求,并不需要真正存储如此耗费空间的存储结构.比如查询一个图上是否包含一条一个节点指向另一个节点的 路径,以及最少经过几个节点就可以到达.对于这种查询,给定一个节点 v∈V,只要能查询出 out(v)的结果,就可以 使用 dijkstra 算法计算出结果.对于图数据上的查询,可以对原始存储结构进行压缩或者构造一种占用存储空间 更加小的结构来存储数据,在图上进行查询时,通过简单的计算就可以得到查询结果,这种技术被称为支持查询 的图数据压缩技术.评价这种技术通常包括两个指标:压缩率和查询时间.压缩率表示压缩后的存储空间与图中 边数的比,用 bpe(bit per edge)表示;查询时间表示判断给定两个节点之间是否存在边需要的时间,单位通常为μs (microsecond). 1.2 图数据压缩技术的发展历程及分类 已知的最早进行支持查询的图数据压缩技术方向研究的是文献[23],该文献中的方法将原图分割为若干子 图,每个子图中的节点可以构造一个线性布局(linear layout)以满足子图中节点之间的边互不相交,该方法需要 O(gn) bit 的存储空间(g 表示图中子图的个数),对节点的邻居查询可以在 O(g+tlog(n))时间完成(t 表示邻居的个 数).之后,文献[24,25]对该算法进行了优化,将邻居查询的复杂度改进为 O(g+t),同时可以支持查询节点的度,也 可以在 O(g)时间内查询两个节点是否相连.这些早期的算法,更多的是在理论上对压缩问题进行分析,在实际应 用中并没有特别好的效果. 从 2000 年开始,随着网络技术的飞速发展,大规模图数据压缩技术越来越受到人们的重视.文献[26−28]使 用将原图分割的方法进行压缩,但均不能满足较快的查询.文献[2,29]提出了一种根据图中节点和链接具有相似 性的特点进行压缩的方法,文献[21,22]在此基础上提出了 BV 算法,该方法通过对网页图中的 URL 按照字典顺 序进行排序,由于顺序相近的 URL 往往包含比较相似的邻居,利用这个性质,BV 算法对网页图的压缩取得了非 常好的效果.文献[30−32]先后对 BV 算法在存储空间和访问速度上作进一步优化.文献[33]提出了 VNM 算法, 3 4 1 6 2 5 1 0 1 1 1 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 2 3 4 5 6 1 3 4 null 1 3 4 null 4 5 null 3 4 5 null6 null 4 5 null (b) (c)(a) 1940 Journal of Software 软件学报 Vol.25, No.9, September 2014 可以在不影响查询结果的情况下将原图转换为边数更少的图,再结合 BV 算法,可以进一步减少存储空间.文献 [34]提出了 AMN 算法,将排序后的 URL 按照域(domain)进行分块,利用域内节点间关系的冗余,获得了较高的压 缩率. 网页图可以通过简单的节点排序对图数据进行压缩,但对于其他类型的图数据,例如社交网络对应的图中 节点,并没有字典顺序的概念,因此无法通过简单的方法找到可以用以压缩的特性.文献[35]提出的 FRS 算法,定 义了一种对图中的节点进行重新排序的方法,使排序后的节点也体现出和网页图类似性质,将重排序后的图再 使用 BV 算法可以进行有效的压缩.文献[36]提出了 BFS 算法,同样采用节点重新排序的方法,利用排序后邻接 表中相邻行的差异来存储图数据,以实现压缩的目的.文献[37,38]提出的 DSM 算法,通过发现图中的稠密图 (dense graph),将原图分割为多个稠密图和一个稀疏图,对稠密图使用特殊的存储结构实现压缩. 通过发掘图数据的内在属性,可以对图数据进行压缩.但并不是所有的图数据都具有某种利于压缩的属性, 而且发现这些属性也需要非常大的代价.因此直接压缩传统的图数据存储结构的方法也非常值得研究.传统的 图数据存储结构主要包括关联矩阵和邻接表.文献[39]提出的 K2 树(K2-tree)算法,使用一种树形结构来存储关联 矩阵,将全为 0 的子矩阵只用树中一个节点表示,由于关联矩阵中大多数元素为 0,这种方法有效地节省了存储 空间.文献[40]根据图数据对应的邻接表构造一段字符序列,使用 Re-Pair[41]和 LZ78[42]算法对字符序列进行压 缩,以达到压缩图数据的目的. 上面提到的压缩方法,在对数据进行压缩的时候,都没有考虑在压缩后的数据上使用哪种方式进行查询.文 献[43]提出的 MPk 算法针对需要同时满足内邻和外邻查询的需求设计了一种特殊的存储结构,已有的算法如果 想要同时支持内邻和外邻查询,需要把原始图和其对应的转置同时进行压缩,而这一方法不需要处理原始图对 应的转置,并且对内邻和外邻的查询可以达到亚线性时间复杂度.文献[44]提出的 QPGC 算法,针对可达性查询 和图模式查询分别设计了不同的压缩方法,该算法通过特定的查询将原图转换为一个新的比原来规模更小的 图,再使用已有的压缩技术进行压缩,可以进一步提高压缩效率. 本文将图数据压缩技术的研究分为如图 2 所示的 4 类:基于传统存储结构的压缩技术、网页图压缩技术、 社交网络图压缩技术和面向特定查询的图压缩技术. Fig.2 Classification and proposed time of graph data compression technology 图 2 图数据压缩技术分类与提出时间 2 基于传统存储结构的压缩技术 传统的图数据存储结构主要包括关联矩阵,如图 1(a)所示,邻接表如图 1(b)所示.关联矩阵使用矩阵表示图 中各节点的关系,对于包含 n 个节点的图,图中的节点为 V={v1,v2,…,vn},使用矩阵{aij}表示图中边的信息.矩阵中 的值用 0 或者 1 表示,如果 aij 为 1,则表示 E 包含一条节点 vi 到节点 vj 的边 e(vi,vj),如果 aij 为 0,则表示没有这样 的边.邻接表是一种链式存储结构,图中的每个节点 vi 对应着一个链 adj(vi)={vi,1,vi,2,…,vi,ai},这个链中存储依次 基于传统存储结的 压缩技术 图数据压缩技术 网页图 压缩技术 面向特定查询的 压缩技术 关联矩阵 邻接表 K2-tree (2009) Re-Pair (2010) BV (2004) AMN (2008) K2-Partitioned (2011) FRS (2009) BFS (2009) MPk (2010) QPGC (2012) 社交网络 压缩技术 LZ78 (2010) DSM (2011) VNM (2008) 张宇 等:图数据表示与压缩技术综述 1941 存储着vi 指向的所有节点,其中vi,j
还剩15页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 6 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

bgn4

贡献于2015-05-11

下载需要 6 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf