时序图数据处理技术研究

发布时间：2018-05-21 09:14

本文选题：时序图 + 图存储　；参考：《清华大学》2015年博士论文

【摘要】：时序图在普通的图的基础上加入了时间维度信息,包含了图的演化历史,能够为应用提供图在不同历史时刻下的信息,为通信网络、社交网络等研究方向的数据分析和算法设计提供了更加丰富的数据支持。与普通图数据相比,时序图数据在存储、查询和计算等方面存在新的挑战。首先,时序图数据的存储与查询在空间复杂度和时间复杂度上存在矛盾,如何对两者进行权衡是系统设计面临的重要问题。其次,普通图数据已经表现出很强的随机访问特征,时序图数据在图的结构维度和时间维度的交错使问题更加复杂,如何利用好数据局部性是时序图系统性能的关键。本文对时序图数据的存储、查询与计算进行了研究,主要工作包括：1.时序图数据管理系统Auxo用于时序图数据的存储和查询,提出了以空间—时间数据块为基本单元的数据组织形式,探索了与之配套的时间分割策略,通过理论分析证明该方案在匀速增长的时序图数据上能够使系统在空间开销和时间开销上都获得线性复杂度。引入图分割机制可以进一步降低最坏情况的时间开销。同时,在数据块内部的布局调整可以提高基于遍历的图查询操作的性能。实验表明,与现有技术相比,在占用存储空间大小相当的前提下,Auxo在时序图的全局查询上取得了2.9-12.1倍的性能提升,在局部查询上取得了1.7-2.7倍的性能提升。2.时序图分析系统Chronos用于时序图数据的分析计算,比较了划分并行和快照并行方式的优劣,针对分布式环境提出了混合并行方式,综合考虑数据局部性、计算调度和通信开销,能够提高计算性能。实验表明,与现有技术相比,Chronos在性能上有一个数量级以上的提升。本文提出的时序图处理方案充分考虑了时序图数据的宏观变化趋势和内在的局部性,在存储、查询和计算等各方面提出了优化的设计,取得了良好的性能与成本优化效果。
[Abstract]:Sequence diagram adds time dimension information to the common graph, which includes the evolution history of the graph, which can provide the information of the graph at different historical times for the application and the communication network. The data analysis and algorithm design of social network provide more abundant data support. Compared with normal graph data, timing diagram data has new challenges in storage, query and computation. Firstly, the storage and query of sequence diagram data are contradictory in space complexity and time complexity. How to balance them is an important problem in system design. Secondly, the common graph data has shown a strong random access feature, and the interlacing of the structural dimension and time dimension makes the problem more complex. How to make good use of the data locality is the key to the performance of the timing diagram system. In this paper, the storage, query and calculation of sequential diagram data are studied. The main work includes: 1. 1. The timing chart data management system (Auxo) is used to store and query the timing diagram data. The spatial and temporal data block is used as the basic unit to organize the data, and the corresponding time division strategy is explored. Through theoretical analysis, it is proved that the proposed scheme can achieve linear complexity in both space and time overhead on the uniform growth sequence diagram data. The time cost of the worst-case scenario can be further reduced by introducing the graph segmentation mechanism. At the same time, the layout adjustment inside the data block can improve the performance of graph query operation based on traversal. The experimental results show that Auxo achieves 2.9-12.1 times performance improvement in global query of timing diagram and 1.7-2.7 times performance improvement in local query on the premise that the storage space is equal to that of the prior art. The simulation results show that Auxo achieves a performance improvement of 2.9-12.1 times on the global query of the timing diagram, and 1.7-2.7 times on the local query. The timing diagram analysis system (Chronos) is used for the analysis and calculation of timing diagram data. The advantages and disadvantages of parallel partitioning and snapshot parallelism are compared. A hybrid parallel method is proposed for distributed environment, considering data locality, scheduling and communication overhead. It can improve the computing performance. The experimental results show that the performance of Chronos is more than one order of magnitude higher than that of the prior art. In this paper, the sequence diagram processing scheme takes full account of the macroscopic changing trend and inherent locality of the sequence diagram data, and puts forward the optimized design in storage, query and calculation, and obtains good performance and cost optimization results.
【学位授予单位】：清华大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP391.41

【相似文献】