發(fā)布時(shí)間：2018-05-21 09:14

  本文選題：時(shí)序圖 + 圖存儲(chǔ)　； 參考：《清華大學(xué)》2015年博士論文

【摘要】：時(shí)序圖在普通的圖的基礎(chǔ)上加入了時(shí)間維度信息,包含了圖的演化歷史,能夠?yàn)閼?yīng)用提供圖在不同歷史時(shí)刻下的信息,為通信網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等研究方向的數(shù)據(jù)分析和算法設(shè)計(jì)提供了更加豐富的數(shù)據(jù)支持。與普通圖數(shù)據(jù)相比,時(shí)序圖數(shù)據(jù)在存儲(chǔ)、查詢和計(jì)算等方面存在新的挑戰(zhàn)。首先,時(shí)序圖數(shù)據(jù)的存儲(chǔ)與查詢?cè)诳臻g復(fù)雜度和時(shí)間復(fù)雜度上存在矛盾,如何對(duì)兩者進(jìn)行權(quán)衡是系統(tǒng)設(shè)計(jì)面臨的重要問題。其次,普通圖數(shù)據(jù)已經(jīng)表現(xiàn)出很強(qiáng)的隨機(jī)訪問特征,時(shí)序圖數(shù)據(jù)在圖的結(jié)構(gòu)維度和時(shí)間維度的交錯(cuò)使問題更加復(fù)雜,如何利用好數(shù)據(jù)局部性是時(shí)序圖系統(tǒng)性能的關(guān)鍵。本文對(duì)時(shí)序圖數(shù)據(jù)的存儲(chǔ)、查詢與計(jì)算進(jìn)行了研究,主要工作包括：1.時(shí)序圖數(shù)據(jù)管理系統(tǒng)Auxo用于時(shí)序圖數(shù)據(jù)的存儲(chǔ)和查詢,提出了以空間—時(shí)間數(shù)據(jù)塊為基本單元的數(shù)據(jù)組織形式,探索了與之配套的時(shí)間分割策略,通過理論分析證明該方案在勻速增長的時(shí)序圖數(shù)據(jù)上能夠使系統(tǒng)在空間開銷和時(shí)間開銷上都獲得線性復(fù)雜度。引入圖分割機(jī)制可以進(jìn)一步降低最壞情況的時(shí)間開銷。同時(shí),在數(shù)據(jù)塊內(nèi)部的布局調(diào)整可以提高基于遍歷的圖查詢操作的性能。實(shí)驗(yàn)表明,與現(xiàn)有技術(shù)相比,在占用存儲(chǔ)空間大小相當(dāng)?shù)那疤嵯?Auxo在時(shí)序圖的全局查詢上取得了2.9-12.1倍的性能提升,在局部查詢上取得了1.7-2.7倍的性能提升。2.時(shí)序圖分析系統(tǒng)Chronos用于時(shí)序圖數(shù)據(jù)的分析計(jì)算,比較了劃分并行和快照并行方式的優(yōu)劣,針對(duì)分布式環(huán)境提出了混合并行方式,綜合考慮數(shù)據(jù)局部性、計(jì)算調(diào)度和通信開銷,能夠提高計(jì)算性能。實(shí)驗(yàn)表明,與現(xiàn)有技術(shù)相比,Chronos在性能上有一個(gè)數(shù)量級(jí)以上的提升。本文提出的時(shí)序圖處理方案充分考慮了時(shí)序圖數(shù)據(jù)的宏觀變化趨勢和內(nèi)在的局部性,在存儲(chǔ)、查詢和計(jì)算等各方面提出了優(yōu)化的設(shè)計(jì),取得了良好的性能與成本優(yōu)化效果。
[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.
【學(xué)位授予單位】：清華大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2015
【分類號(hào)】：TP391.41

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李勇華;毋國慶;劉小麗;張帆;;從時(shí)序圖描述推導(dǎo)目標(biāo)描述的方法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2007年03期

2 陳錦富;盧炎生;謝曉東;;一種基于事務(wù)時(shí)序圖的惡意事務(wù)檢測算法[J];計(jì)算機(jī)集成制造系統(tǒng);2008年06期

3 劉剛;羅愛民;皇甫先鵬;;作戰(zhàn)事件跟蹤描述建模及驗(yàn)證方法研究[J];計(jì)算機(jī)科學(xué);2012年05期

4 陳錦富;孫凡博;;數(shù)據(jù)庫防攻擊的合法事務(wù)時(shí)序圖自動(dòng)生成方法[J];武漢大學(xué)學(xué)報(bào)(工學(xué)版);2009年03期

5 劉育明;劉德民;;數(shù)字邏輯電路真值表和時(shí)序圖測量方法的研究[J];西安工程大學(xué)學(xué)報(bào);1991年04期

6 張媛;;電力公司人力資源管理系統(tǒng)[J];數(shù)字技術(shù)與應(yīng)用;2013年07期

7 胡渭清,呂以全;PLC輸出特大空占比方波的三種編程方案[J];天津理工學(xué)院學(xué)報(bào);2000年01期

8 王新民;根據(jù)時(shí)序圖編寫接口軟件的方法[J];自動(dòng)化博覽;1998年06期

9 徐景輝,劉文海,張根度;基于Time Petri Nets的UML時(shí)序圖分析[J];計(jì)算機(jī)工程;2005年19期

10 周航;黃志球;王莉;;基于多態(tài)性的UML時(shí)序圖度量研究[J];南京航空航天大學(xué)學(xué)報(bào);2006年06期

相關(guān)會(huì)議論文 前1條

1 介龍梅;徐麗;谷文祥;;基于啟發(fā)式策略的時(shí)序圖規(guī)劃研究[A];2005年全國理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2005年

相關(guān)博士學(xué)位論文 前1條

1 韓文_";時(shí)序圖數(shù)據(jù)處理技術(shù)研究[D];清華大學(xué);2015年

相關(guān)碩士學(xué)位論文 前2條

1 崔康樂;UML時(shí)序圖模型到UPPAAL時(shí)間自動(dòng)機(jī)模型轉(zhuǎn)換方法研究和工具實(shí)現(xiàn)[D];華東師范大學(xué);2011年

2 陳艷;重慶職業(yè)信息學(xué)院績效考評(píng)系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];電子科技大學(xué);2011年

，

本文編號(hào)：1918587