论文部分内容阅读
随着互联网的快速发展和大数据时代的到来,人们不仅需要考虑日益严峻的数据存储问题,更要考虑如何对大规模数据进行分析和处理,从而挖掘数据中具有潜在价值的信息。图数据是社交网络、万维网和生物信息等应用的抽象数据模型,这些应用正面临着规模快速增长和形式复杂多样的巨大挑战。紧凑的图数据表示是图数据高效管理和分析的前提,不仅可以降低图数据的存储空间,而且还可以支持图数据的快速处理,具有重要的学术意义和实际价值。本文基于聚类机制对大规模图数据表示方法做了相关研究,提出了一种新型的数据压缩表示方法,主要研究内容如下:(1)提出了一种基于稠密网格聚类算法DGC。首先对现有的基于K~2-tree和K~2-BDC的图数据划分方法作了深入研究,依据这两种方法存在的无法聚类邻接矩阵中所有1值的不足,提出了基于稠密网格聚类算法DGC。该算法实现了对邻接矩阵中所有1值的聚类重组,提高了矩阵的密度。此外在此理论基础上对该算法的参数设定上做了优化处理。实验表明,对于不同类型、不同规模的图数据集,稠密网格聚类算法DGC能够筛选出图中所有的1值并将其聚类,且均有显著的聚类效果。(2)将稠密网格聚类算法DGC与K~2-tree技术相结合,提出了一种新的图数据压缩表示方法DGC-K~2-tree。首先使用稠密网格聚类算法DGC将图数据进行聚类重组,生成多个稠密的重组矩阵。然后将这多个重组矩阵表示为K~2-tree,充分压缩了图的邻接矩阵中包含的空白区域,达到进一步压缩图数据存储空间的目的。实验表明,在存储效率方面,与对比算法中表现最佳的方法K~2-BDC相比,本文方法平均减少了34.07%的存储空间。(3)在实现图数据压缩表示的基础上,提出了基于DGC-K~2-tree的图查询算法,该算法能够查询给定结点的所有邻接结点,能够查询结点间的连通性。此外,算法通过降低K~2-tree的高度,减少了查询操作的递归访问次数,进而缩短了查询时间。实验表明,在查询效率方面,与对比算法中表现最佳的方法LZ78相比,本文方法平均缩短了80.63%的查询时间。