本文關(guān)鍵詞：動態(tài)有向圖上面向最短路徑查詢的新型概要技術(shù)研究

  更多相關(guān)文章： 動態(tài)有向圖 最短路徑 概要技術(shù) 近似查詢 增量計算

【摘要】：近年來,隨著有向圖最短路徑查詢應(yīng)用在路網(wǎng)、計算機(jī)網(wǎng)絡(luò)和社交網(wǎng)絡(luò)等數(shù)據(jù)中的應(yīng)用不斷增加,有向圖的最短路徑查詢技術(shù)受到更加廣泛的關(guān)注�，F(xiàn)有技術(shù)可以高效的處理無向圖環(huán)境下的最短路徑查詢,然而由于有向圖上最短路徑查詢操作的特殊性使得在有向圖上的最短路徑查詢操作遇到了很大的挑戰(zhàn),有向圖最短路徑查詢并無很好的解決方案。本文研究面向有向圖準(zhǔn)確的和帶有精度保證的最短路徑查詢信息概要技術(shù),并提出動態(tài)圖環(huán)境下相應(yīng)概要增量維護(hù)算法。首先,針對現(xiàn)有有向圖最短路徑查詢技術(shù)在計算過程中在精度和速度上的缺陷,本文在代表點(diǎn)策略的基礎(chǔ)上提出基于生成樹編碼概要結(jié)構(gòu),通過代表點(diǎn)策略降低內(nèi)存負(fù)載極大加快概要構(gòu)建速度和查詢速度；同時針對通過概要結(jié)構(gòu)覆蓋全部查詢概要結(jié)構(gòu)構(gòu)建過程中頻繁I/O的缺陷,改進(jìn)其磁盤索引結(jié)構(gòu)提出輕量級的概要結(jié)構(gòu)；在證明準(zhǔn)確概要查詢結(jié)果有效性的前提下,本文提出了相應(yīng)的I/O高效構(gòu)建算法和查詢算法,并通過實驗對準(zhǔn)確概要結(jié)構(gòu)性能進(jìn)行驗證。其次,對于用戶要求在短時間內(nèi)獲取帶有誤差保證最短距離的應(yīng)用請求,本文提出基于拓?fù)鋵拥碾x散landmark快速概要結(jié)構(gòu),通過landmark節(jié)點(diǎn)的拓?fù)鋵哟魏拖嚓P(guān)信息,可以降低搜索數(shù)據(jù)大小并提前終結(jié)不必要的查詢,進(jìn)而加快查詢速度；針對查詢時在離散landmark節(jié)點(diǎn)集合搜索代價較大的缺陷,本文依照二分索引思想組織landmark節(jié)點(diǎn)構(gòu)建近似概要,并針對此概要結(jié)構(gòu)提出近似概要構(gòu)建算法和有精度保障的查詢算法；最終在真實數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行大量的實驗,驗證近似概要結(jié)構(gòu)和相應(yīng)查詢算法的有效性。最后,本文對概要結(jié)構(gòu)的高效查詢和動態(tài)圖環(huán)境下概要增量維護(hù)操作進(jìn)行研究,為了降低整體查詢代價以及動態(tài)圖環(huán)境下概要增量維護(hù)代價,本文設(shè)計離散磁盤結(jié)構(gòu)存儲Triad信息；同時在離散磁盤結(jié)構(gòu)的基礎(chǔ)上提出增量維護(hù)緩存結(jié)構(gòu)降低平均增量維護(hù)代價,并通過攤還分析證明緩存結(jié)構(gòu)的有效性；最后提出基于離散磁盤結(jié)構(gòu)信息獲取算法和增量維護(hù)算法,并通過實驗證明其有效性。本文從實際應(yīng)用中對有向圖最短路徑查詢的典型特征和調(diào)整進(jìn)行分析,針對有向圖最短路徑概要相關(guān)技術(shù)進(jìn)行研究,提出如代表點(diǎn)策略概要、有精度保障的近似概要以及概要結(jié)構(gòu)增量維護(hù)等關(guān)鍵技術(shù)處理不同應(yīng)用場景下的有向圖最短路徑查詢應(yīng)用。本文的概要結(jié)構(gòu)以更少的內(nèi)存和更短的預(yù)處理時間處理更大規(guī)模的圖數(shù)據(jù),并且以更快的速度返回最短路徑查詢結(jié)果。
【關(guān)鍵詞】：動態(tài)有向圖 最短路徑 概要技術(shù) 近似查詢 增量計算
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：TP333.35
【目錄】：

• 摘要5-6
• ABSTRACT6-11
• 第1章 引言11-15
• 1.1 圖最短路徑基本概念及應(yīng)用11-12
• 1.2 研究背景12-13
• 1.2.1 最短路徑索引技術(shù)12
• 1.2.2 最短路徑概要技術(shù)12-13
• 1.3 問題提出13
• 1.4 本文貢獻(xiàn)13-14
• 1.5 本文工作和組織結(jié)構(gòu)14-15
• 第2章 相關(guān)工作概述15-21
• 2.1 Naive最短路徑查詢策略15-16
• 2.2 最短路徑索引技術(shù)16-18
• 2.2.1 有向圖最短路徑索引技術(shù)16-17
• 2.2.2 無向圖最短路徑索引技術(shù)17-18
• 2.3 圖概要與圖壓縮技術(shù)18-19
• 2.3.1 最短路徑概要技術(shù)18-19
• 2.3.2 圖壓縮技術(shù)19
• 2.4 結(jié)論19-21
• 第3章 基于代表點(diǎn)策略無損概要21-45
• 3.1 引言21
• 3.2 C-RTI無損概要模型21-27
• 3.2.1 基于路徑距離主干節(jié)點(diǎn)策略概要模型22-23
• 3.2.2 生成樹編碼23-26
• 3.2.3 RTI概要性質(zhì)26-27
• 3.3 Q-RTI無損概要27-30
• 3.3.1 不完備Triad編碼27-29
• 3.3.2 基于覆蓋范圍均等采樣策略29-30
• 3.4 無損概要構(gòu)建與查詢算法30-36
• 3.4.1 C-RTI概要構(gòu)建算法30-32
• 3.4.2 Q-RTI概要構(gòu)建策略32-34
• 3.4.3 Naive概要查詢算法34-35
• 3.4.4 概要構(gòu)建代價分析35-36
• 3.5 實驗36-44
• 3.5.1 相關(guān)技術(shù)分析37-38
• 3.5.2 真實數(shù)據(jù)集概要性能38-40
• 3.5.3 模擬數(shù)據(jù)集概要性能40-44
• 3.6 結(jié)論44-45
• 第4章 基于拓?fù)鋵哟谓聘乓?/span>45-67
• 4.1 引言45-49
• 4.1.1 傳統(tǒng)最短路徑快速概要技術(shù)45-46
• 4.1.2 基于無向圖近似概要技術(shù)缺陷46-49
• 4.2 Naive-TL快速概要模型49-52
• 4.2.1 離散landmark49-50
• 4.2.2 Naive-TL概要結(jié)構(gòu)50-52
• 4.3 BTL快速概要52-59
• 4.3.1 BTL快速概要概述52-53
• 4.3.2 二分拓?fù)鋵哟蝜andmark快速概要查詢53-54
• 4.3.3 BTL概要概要構(gòu)建與查詢算法54-58
• 4.3.4 BTL概要性能58-59
• 4.4 實驗59-66
• 4.4.1 真實數(shù)據(jù)集概要性能分析60-62
• 4.4.2 真實數(shù)據(jù)集BTL層數(shù)對概要性能的影響62-64
• 4.4.3 模擬數(shù)據(jù)集BTL概要性能64-66
• 4.5 結(jié)論66-67
• 第5章 概要高效動態(tài)維護(hù)與查詢67-85
• 5.1 引言67-68
• 5.2 離散磁盤概要與查詢操作68-73
• 5.2.1 離散磁盤編碼結(jié)構(gòu)68-71
• 5.2.2 C-RTI/Q-RTI概要查詢71-72
• 5.2.3 BTL概要查詢72-73
• 5.3 動態(tài)圖概要結(jié)構(gòu)概述73-76
• 5.3.1 動態(tài)圖操作分類73-74
• 5.3.2 概要結(jié)構(gòu)增量維護(hù)分析74-76
• 5.4 基于離散磁盤結(jié)構(gòu)概要維護(hù)76-80
• 5.4.1 C-RTI/Q-RTI概要增量維護(hù)76-77
• 5.4.2 BTL概要更新77-78
• 5.4.3 增量維護(hù)Buffer結(jié)構(gòu)78-80
• 5.5 實驗80-83
• 5.5.1 真實數(shù)據(jù)集概要查詢與增量計算性能81-82
• 5.5.2 BTL概要層次數(shù)對概要更新代價的影響82-83
• 5.6 結(jié)論83-85
• 第6章 結(jié)論85-87
• 6.1 本文主要貢獻(xiàn)與結(jié)論85
• 6.2 進(jìn)一步的工作85-87
• 參考文獻(xiàn)87-91
• 致謝91-93
• 攻讀碩士學(xué)位期間的項目情況93

【相似文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 孟祥清;長度遞增法求最短路徑[J];河北能源職業(yè)技術(shù)學(xué)院學(xué)報;2002年04期

2 傅清祥,王朝利,孫劍峰;長廊最短路徑的最優(yōu)算法[J];計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報;2002年12期

3 王濤,李偉生;最短路徑子圖[J];北方交通大學(xué)學(xué)報;2004年02期

4 徐鳳生;最短路徑的求解算法[J];計算機(jī)應(yīng)用;2004年05期

5 王濤,李偉生;低代價最短路徑樹的快速算法[J];軟件學(xué)報;2004年05期

6 宣士斌;基于分流算法的最短路徑求解算法[J];計算機(jī)工程與應(yīng)用;2004年20期

7 徐鳳生;李天志;;所有最短路徑的求解算法[J];計算機(jī)工程與科學(xué);2006年12期

8 白青海;;一種求解交通圖最短路徑的方案[J];內(nèi)蒙古民族大學(xué)學(xué)報(自然科學(xué)版);2007年02期

9 章昭輝;;一種基于離散變權(quán)網(wǎng)絡(luò)的動態(tài)最短路徑快速算法[J];計算機(jī)科學(xué);2010年04期

10 原慧琳;汪定偉;;最短路徑的可達(dá)矩陣算法[J];信息與控制;2011年02期

中國重要會議論文全文數(shù)據(jù)庫 前10條

1 溫粉蓮;唐常杰;喬少杰;許剛;劉威;左R，

本文編號：822555