本文關(guān)鍵詞：面向位置服務(wù)的最短路徑緩存算法及其優(yōu)化方法，，由筆耕文化傳播整理發(fā)布。

【摘要】：隨著互聯(lián)網(wǎng)與信息化技術(shù)的迅速發(fā)展,特別是近年來(lái),隨著移動(dòng)終端技術(shù)、無(wú)線網(wǎng)絡(luò)技術(shù)、移動(dòng)通信技術(shù)的飛速發(fā)展,促使了移動(dòng)互聯(lián)網(wǎng)的產(chǎn)生和快速的發(fā)展。人們?cè)谌粘Ｉ钪袑?duì)于信息獲取的及時(shí)性和有效性的需求也越來(lái)越強(qiáng)烈,促使了基于位置服務(wù)(Location-based Services)的產(chǎn)生和快速發(fā)展。路網(wǎng)上的最短路徑查詢作為一種基本的基于位置的服務(wù),受到了越來(lái)越多的關(guān)注。作為網(wǎng)絡(luò)服務(wù)的重要組成部分,網(wǎng)絡(luò)緩存在減少查詢響應(yīng)時(shí)間,提高系統(tǒng)效率方面有著重要的作用。因此如何利用網(wǎng)絡(luò)緩存來(lái)提高路網(wǎng)上的最短路徑查詢效率成為一項(xiàng)很有挑戰(zhàn)性的研究工作�，F(xiàn)有的支持最短路徑查詢的緩存技術(shù)分為動(dòng)態(tài)緩存技術(shù)和靜態(tài)緩存技術(shù)。動(dòng)態(tài)緩存技術(shù)在系統(tǒng)的運(yùn)行過(guò)程中動(dòng)態(tài)的更新緩存中存儲(chǔ)的最短路徑,但是存儲(chǔ)的路徑響應(yīng)查詢的效率較低,空間利用率不高,需要?jiǎng)討B(tài)的更新緩存,并行性較差。靜態(tài)緩存技術(shù)通過(guò)分析查詢記錄的統(tǒng)計(jì)信息來(lái)離線的構(gòu)建緩存,但是對(duì)查詢依賴性較大,對(duì)查詢的適應(yīng)性較差。因此本文重點(diǎn)研究支持最短路徑查詢的緩存構(gòu)建技術(shù)。本文首先綜述了現(xiàn)有的支持最短路徑查詢的緩存相關(guān)的技術(shù),分析了現(xiàn)有技術(shù)的不足之處。為了定量的描述最短路徑的緩存收益,基于最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì),本文首先定義了一種緩存收益模型來(lái)指導(dǎo)緩存的構(gòu)建過(guò)程,以解決緩存收益定量描述的問(wèn)題�；诰彺媸找婺Ｐ�,本文提出了一種全新的用于最短路徑緩存構(gòu)建的SPEC算法,以構(gòu)建支持最短路徑查詢的緩存,從而有效地提高了緩存的空間利用率和查詢命中率。針對(duì)緩存離線構(gòu)建的冗余計(jì)算問(wèn)題,本文提出了SPEC算法的改進(jìn)方法,并對(duì)SPEC算法進(jìn)行了改進(jìn),以進(jìn)一步提高緩存的構(gòu)建效率。提出了一種基于倒排索引結(jié)構(gòu)的最短路徑緩存索引結(jié)構(gòu),并設(shè)計(jì)了索引構(gòu)建和查詢的算法,有效地支持最短路徑子路徑的查詢問(wèn)題,提高了查詢的效率。最后,在真實(shí)的路網(wǎng)數(shù)據(jù)集上進(jìn)行了大量測(cè)試研究,通過(guò)實(shí)驗(yàn)結(jié)果本身及對(duì)實(shí)驗(yàn)結(jié)果的分析,證明了本文提出的緩存收益模型能夠有效地衡量緩存的收益；SPEC算法能夠有效的構(gòu)建最短路徑緩存,提高了緩存的空間利用率和查詢的命中率。
【關(guān)鍵詞】：緩存 最短路徑查詢 路網(wǎng) 面向位置的服務(wù) 收益模型
【學(xué)位授予單位】：東北大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2014
【分類號(hào)】：TP333
【目錄】：

• 摘要5-6
• Abstract6-10
• 第1章 緒論10-14
• 1.1 研究背景10-11
• 1.2 本文的研究?jī)?nèi)容及面臨的挑戰(zhàn)11-12
• 1.3 本文的貢獻(xiàn)12
• 1.4 本文的組織結(jié)構(gòu)12-14
• 第2章 相關(guān)工作14-26
• 2.1 網(wǎng)絡(luò)查詢的緩存方法14-17
• 2.1.1 動(dòng)態(tài)緩存方法14-15
• 2.1.2 靜態(tài)緩存方法15-16
• 2.1.3 混合緩存方法16-17
• 2.2 最短路徑查詢問(wèn)題17-22
• 2.2.1 最短路徑查詢算法17-20
• 2.2.2 圖的索引結(jié)構(gòu)20-22
• 2.3 搜索引擎索引介紹22-25
• 2.4 本章小結(jié)25-26
• 第3章 背景知識(shí)及問(wèn)題定義26-34
• 3.1 基本概念26-31
• 3.1.1 圖和最短路徑基本概念26-30
• 3.1.2 緩存相關(guān)基本概念30-31
• 3.2 基于緩存查詢的系統(tǒng)的處理過(guò)程31-32
• 3.3 問(wèn)題定義32-33
• 3.4 本章小結(jié)33-34
• 第4章 最短路徑緩存收益模型34-44
• 4.1 查詢?nèi)罩镜慕y(tǒng)計(jì)分析34-36
• 4.2 路徑查詢代價(jià)基準(zhǔn)36-37
• 4.3 緩存收益模型相關(guān)定義37-40
• 4.4 緩存收益模型優(yōu)化方法40-43
• 4.5 本章小結(jié)43-44
• 第5章 基于收益模型的緩存構(gòu)造算法與優(yōu)化44-56
• 5.1 基于收益模型的緩存構(gòu)造算法44-48
• 5.1.1 算法思想44-45
• 5.1.2 算法實(shí)現(xiàn)與分析45-48
• 5.2 算法優(yōu)化策略48-50
• 5.3 緩存存儲(chǔ)結(jié)構(gòu)及優(yōu)化策略50-54
• 5.4 本章小結(jié)54-56
• 第6章 實(shí)驗(yàn)與分析56-64
• 6.1 實(shí)驗(yàn)設(shè)置56-57
• 6.2 收益模型實(shí)驗(yàn)與分析57-58
• 6.3 代理模式下緩存方法實(shí)驗(yàn)與分析58-60
• 6.4 服務(wù)模式下緩存方法實(shí)驗(yàn)與分析60-62
• 6.5 本章小結(jié)62-64
• 第7章 結(jié)束語(yǔ)64-66
• 7.1 本文總結(jié)64
• 7.2 工作展望64-66
• 參考文獻(xiàn)66-68
• 致謝68-70
• 攻碩期間參加的項(xiàng)目及發(fā)表的論文70

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

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

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

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

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

本文編號(hào)：439869