面向位置服務(wù)的最短路徑緩存算法及其優(yōu)化方法.pdf

1、隨著互聯(lián)網(wǎng)與信息化技術(shù)的迅速發(fā)展，特別是近年來，隨著移動終端技術(shù)、無線網(wǎng)絡(luò)技術(shù)、移動通信技術(shù)的飛速發(fā)展，促使了移動互聯(lián)網(wǎng)的產(chǎn)生和快速的發(fā)展。人們在日常生活中對于信息獲取的及時性和有效性的需求也越來越強烈，促使了基于位置服務(wù)(Location-based Services)的產(chǎn)生和快速發(fā)展。路網(wǎng)上的最短路徑查詢作為一種基本的基于位置的服務(wù)，受到了越來越多的關(guān)注。作為網(wǎng)絡(luò)服務(wù)的重要組成部分，網(wǎng)絡(luò)緩存在減少查詢響應(yīng)時間，提高系統(tǒng)效率方面有著重

2、要的作用。因此如何利用網(wǎng)絡(luò)緩存來提高路網(wǎng)上的最短路徑查詢效率成為一項很有挑戰(zhàn)性的研究工作。
　　現(xiàn)有的支持最短路徑查詢的緩存技術(shù)分為動態(tài)緩存技術(shù)和靜態(tài)緩存技術(shù)。動態(tài)緩存技術(shù)在系統(tǒng)的運行過程中動態(tài)的更新緩存中存儲的最短路徑，但是存儲的路徑響應(yīng)查詢的效率較低，空間利用率不高，需要動態(tài)的更新緩存，并行性較差。靜態(tài)緩存技術(shù)通過分析查詢記錄的統(tǒng)計信息來離線的構(gòu)建緩存，但是對查詢依賴性較大，對查詢的適應(yīng)性較差。因此本文重點研究支持最短路徑查詢

3、的緩存構(gòu)建技術(shù)。
　　本文首先綜述了現(xiàn)有的支持最短路徑查詢的緩存相關(guān)的技術(shù)，分析了現(xiàn)有技術(shù)的不足之處。為了定量的描述最短路徑的緩存收益，基于最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)，本文首先定義了一種緩存收益模型來指導緩存的構(gòu)建過程，以解決緩存收益定量描述的問題。基于緩存收益模型，本文提出了一種全新的用于最短路徑緩存構(gòu)建的SPEC算法，以構(gòu)建支持最短路徑查詢的緩存，從而有效地提高了緩存的空間利用率和查詢命中率。針對緩存離線構(gòu)建的冗余計算問題，本文