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

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

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

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