1、隨著互聯(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)效率方面有著重

2、要的作用。因此如何利用網(wǎng)絡(luò)緩存來(lái)提高路網(wǎng)上的最短路徑查詢效率成為一項(xiàng)很有挑戰(zhàn)性的研究工作。
　　現(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)研究支持最短路徑查詢

3、的緩存構(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)題，本文