大规模图数据交互式可视化分析的性能优化

摘要

对包含大量节点和边的图数据进行快速、高效地分析与挖掘，是当前图分析领域的热点研究问题。本文在认真研究了国内外现状的基础上，结合现有数据分析技术，并基于增量预计算技术和抽样技术，设计实现了高效的图分析原型系统GASys，随后基于节点的近似度分布分层策略，结合现有图抽样算法设计并实现了一系列的分层图抽样算法，解决了现有图抽样算法在一次抽样过程中存在的有偏性问题，提高了抽样算法的抽样准确度，进一步优化了大规模图数据交互式可视化分析性能。 在统计学中，抽样被作为一种高效的分析方法，常常被用于大规模图数据分析领域，以提升分析性能。经典的图抽样算法大都存在高度节点或低度节点过度入样的问题，极大影响算法抽样性能。复杂图中节点的度服从幂律分布，节点个体之间存在较大差异。本文首次提出节点的近似度分布概念，在此概念基础上设计并实现了一系列分层图抽样算法。在3个真实的图数据集上的实验结果表明，本文提出的分层图抽样算法相比经典图抽样算法，能够保留更多的图拓扑属性，且执行效率比FFS和ES-i更高。理论分析与实验结果均表明本文的分层图抽样算法在度的无偏性方面优于现有算法，同时为图抽样算法中的有偏性问题提供了一种通用、可行的解决方案。 现有的图分析系统大都无法满足大规模图数据分析需求，本文分析研究了当前图分析系统存在的问题，基于增量预计算技术和抽样技术，设计并实现了交互式可视化图分析原型系统 GASys，它允许用户高效地执行可视化图分析任务。GASys 使用数据缓存技术实现数据的增量式加载，提高了系统的交互性能，这使得 GASys 能够完成大规模图数据的分析任务。使用基于缓存的增量预计算技术提高了交互分析性能。使用抽样技术实现数据的非全量分析，在保证算法准确性的前提下，非全量分析更快。GASys 还集成了大量的图路径算法、图抽样算法、图聚类算法，图布局算法等，使得GASys能够适用于不同的应用场景。

目录

第一个书签之前