图数据模型,简称图数据,是表示实体和实体间联系的数据模型。和结构化的关系模型数据以及非结构化数据相比,图数据表达形式多样、灵活,且易于实现。随着互联网技术和各种数据收集和传输技术的发展,越来越多的数据以图的形式建模,以表示互联网中不同结点、不同用户、不同实体之间的联系。同时,搜索引擎、社交网络服务、科学数据分析、知识图谱分析等应用中所需要管理的图数据规模也越来越大。而目前大部分图数据处理算法往往需要将整个数据集存放在内存进行分析。所以,如何减少图数据处理的所需要存储空间容量是图数据管理的重要问题,而图数据压缩是解决这一问题的主要手段之一。图数据压缩不仅需要考虑压缩率,即压缩后数据与原始数据规模的比值,还需要考虑压缩方法的运行效率。另一方面,在对压缩后的数据进行处理时,如何避免不必要的解压缩操作,支持各类图数据查询,提升图数据处理效率,也至关重要。针对以上问题,本文研究支持查询的大规模图数据的无损压缩方法。具体而言,本文的贡献包括以下三点:·提出了一种基于三角形列表的静态图数据无损压缩方法,bound-tri方法。此方法利用图数据中大量存在的三角形子图,合并这些三角形子图中的公共结点,对图数据进行无损压缩。bound-tri方法在三角形列表的过程中过滤了图数据中度较高的一批结点,使得需要压缩的图数据的规模减少,从而降低图数据的压缩时间。同时,bound-tri方法还确保了在三角形列表的结果中只冗余较少的边,并得到一个压缩率较高的压缩结果。bound-tri方法还允许用户在压缩时设置不同的结点度过滤参数来平衡图数据压缩的压缩率、压缩时间,以及压缩结果对反馈图数据查询的效率。本文所介绍的bound-tri方法可以对大规模图数据,尤其是社交网络图,实现高效率的无损压缩。此方法相较大部分已有的图数据无损压缩方法有着较高的压缩率和较短的压缩时间。·提出了一种针对图数据流形式逐步生成的图数据的无损压缩方法,STT方法。STT方法利用图数据流中在短时间内多次输人的结点以及连接这些结点的边,对图数据流进行无损压缩。STT方法在限定大小的缓存中尽可能地使高热度结点以及包含有这些结点的边或三角形集合存活,并在缓存中利用三角形列表算法尽可能多地将图数据流中的三角形子图组成三角形集合,实现了较高的压缩率以及较高的数据流吞吐量。同时,在图数据流的压缩结果中存在一定数量的三角形集合,这可以满足对图数据查询的无解压快速反馈需求。并使相邻时间段内输入的结点尽可能地被包含在一个或极少数个不同的三角形集合中。STT方法在压缩时无需输入完整的图数据拓扑结构或全部图数据内容信息。同样地,用户可以通过参数调整缓存更新的更新效率,对不同速率的图数据流进行压缩,或是通过降低一部分的图数据的压缩率,提高图数据流压缩的吞吐量。STT方法相较目前的静态图数据压缩方法,可以得到与RVE、Re-Pair和VNM等经典的图数据压缩方法近似压缩率的图数据压缩结果,却可以在图数据逐步到达时即开始压缩操作,极大地提升了压缩效率。·提出了在已压缩图数据结果中执行邻接结点查询、k-距离结点查询、共同邻接结点查询这三类基本查询的处理算法。这些算法都保证了不需要对基于三角形子图进行压缩的图数据进行解压缩即可返回查询结果。经bound-tri方法和STT方法压缩得到的图数据中包含大量的三角形子图,且这些子图可以被直接地提取出来,利用这些三角形子图中相互连接的结点以及结点间的边,能实现无需解压的查询反馈。从而在获得容量较小的图数据压缩结果的同时,避免了昂贵的解压缩操作。基于这些算法,可以实现社交网络数据抽样、用户推荐、谣言传播分析等图数据分析任务。目前,经大部分图数据压缩方法压缩得到的图数据,如SLAHSHBURN、BV框架及κκ2-partitioned等方法,均需要在反馈查询时部分或完全地解压图数据。综上所述,本文从图数据压缩问题出发,在静态图数据及图数据流这两类环境中分别对大规模图数据中进行无损压缩的问题进行了研究分析。本文图数据中大量存在的三角形子图并利用结点合并的方法,实现高效的图数据压缩。在静态图数据环境中,在压缩过程中过滤度较高的结点并对其余结点进行了三角形列表计算,实现了较高的压缩率以及较短的压缩时间。在图数据流的环境中,则在数据流缓存中保持高热度结点的存活时间,从图数据流中列出更多的三角形子图,在图数据存储到本地存储空间前,实现对图数据的压缩。另外,本文还研究了在已压缩的图数据中的查询处理算法,证明了基于三角形子图压缩的图数据,如经bound-tri方法和STT方法压缩的图数据,可以在无需解压缩的情况下对几类常用的图数据查询快速返回查询结果。对多个真实的大规模图数据集的压缩实验以及和同类方法的对比表明,本文所提出的方法在压缩率、压缩效率(压缩时间或数据流压缩吞吐量),查询支持这三个方面,具有整体性优势。