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

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

• 摘要5-6
• Abstract6-10
• 第1章 緒論10-14
• 1.1 研究背景10-11
• 1.2 本文的研究內(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 動態(tài)緩存方法14-15
• 2.1.2 靜態(tài)緩存方法15-16
• 2.1.3 混合緩存方法16-17
• 2.2 最短路徑查詢問題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章 背景知識及問題定義26-34
• 3.1 基本概念26-31
• 3.1.1 圖和最短路徑基本概念26-30
• 3.1.2 緩存相關(guān)基本概念30-31
• 3.2 基于緩存查詢的系統(tǒng)的處理過程31-32
• 3.3 問題定義32-33
• 3.4 本章小結(jié)33-34
• 第4章 最短路徑緩存收益模型34-44
• 4.1 查詢?nèi)罩镜慕y(tǒng)計分析34-36
• 4.2 路徑查詢代價基準(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 緩存存儲結(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é)束語64-66
• 7.1 本文總結(jié)64
• 7.2 工作展望64-66
• 參考文獻(xiàn)66-68
• 致謝68-70
• 攻碩期間參加的項(xiàng)目及發(fā)表的論文70

【相似文獻(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

本文編號：439869