時間依賴路網(wǎng)高效k最近鄰查詢混搭機制的研究.pdf

1、時空查詢（如k最近鄰查詢）被廣泛地使用在基于位置服務(wù)(LBS)中，例如查找離我最近的五家飯店。盡管在路網(wǎng)中兩點間的行駛時間非常重要，但已有時空查詢的距離度量大部分都是基于物理距離，即歐幾里得距離或網(wǎng)絡(luò)距離，而這種距離度量并不能反映出行駛時間。但相對于物理距離，行駛時間具有高度動態(tài)性。路網(wǎng)中兩點之間的行駛時間很難被實時而又準(zhǔn)確預(yù)測。獲取行駛時間最佳的方式是實時監(jiān)控道路的交通狀況，如部署攝像頭、傳感器以及收集車輛GPS信息等。然而，并不是每

2、一個LBS提供者都有能力完成這種高代價的部署。
　　因此本文中，我們?yōu)長BS提供者設(shè)計出了一個服務(wù)器端的地圖混搭機制。采用這種地圖混搭機制，LBS提供者利用從互聯(lián)網(wǎng)地圖服務(wù)商（如谷歌地圖、必應(yīng)地圖、雅虎地圖和百度地圖等）獲取的行駛時間和路徑信息并結(jié)合本地數(shù)據(jù)來有效地處理來自用戶的各種基于行駛時間的時空查詢請求?；ヂ?lián)網(wǎng)地圖服務(wù)商擁有足夠的財力和實力，通過多渠道收集數(shù)據(jù)（如實時交通狀況和歷史交通數(shù)據(jù)等）以計算或估算路網(wǎng)中給定兩點間的行

3、駛時間和路徑信息。但是由于從互聯(lián)網(wǎng)地圖服務(wù)商獲取數(shù)據(jù)的高代價性以及局限性，本文提出了修剪、分組、方向共享和并行請求等優(yōu)化算法并結(jié)合k最近鄰查詢特點，來減少LBS提供者向互聯(lián)網(wǎng)地圖服務(wù)商發(fā)送數(shù)據(jù)請求的次數(shù)和響應(yīng)用戶的時間。本文的主要研究內(nèi)容及貢獻總結(jié)如下:
　　為LBS提供者設(shè)計了一個服務(wù)器端的地圖混搭機制。利用該機制，LBS提供者通過從互聯(lián)網(wǎng)地圖服務(wù)商獲取行駛時間和路徑信息，并結(jié)合本地數(shù)據(jù)，有效地處理路網(wǎng)中基于行駛時間的各項時空查

4、詢請求。
　　利用修剪技術(shù)，即在算法執(zhí)行過程中不斷修剪不必要的查詢對象，來減少LBS提供者向互聯(lián)網(wǎng)地圖服務(wù)商發(fā)送數(shù)據(jù)請求的次數(shù)，并結(jié)合網(wǎng)絡(luò)擴展算法來處理k最近鄰查詢請求。
　　設(shè)計出了分組優(yōu)化策略，即把查詢對象和用戶分組到路網(wǎng)中交叉路口以實現(xiàn)共享執(zhí)行，然后估算查詢對象到其對應(yīng)路口的行駛時間和路徑信息。在保證查詢結(jié)果高準(zhǔn)確性的基礎(chǔ)上，該分組算法能大大減少LBS提供者發(fā)送外部數(shù)據(jù)請求的次數(shù)。
　　提出了方向共享策略以進一步

5、減少外部數(shù)據(jù)請求次數(shù)。該策略試圖讓一條包含詳細行駛時間和方向信息的路徑能被多個起點和其對應(yīng)的終點共享使用。為了最大化利用方向共享執(zhí)行，本文中還設(shè)計了一個直方圖方法用以估算一條路徑的共享能力。
　　研究了為相互獨立路徑并行發(fā)送數(shù)據(jù)請求到互聯(lián)網(wǎng)地圖服務(wù)商的策略，以降低LBS提供者響應(yīng)查詢用戶的時間。此外，還充分挖掘了多用戶查詢間合作和增量執(zhí)行以應(yīng)對大規(guī)模用戶查詢請求，同時解決了增量執(zhí)行中可能出現(xiàn)的饑餓問題。
　　對于本文設(shè)計的每