基于關鍵詞的最優(yōu)路徑查詢高效處理方法的研究.pdf

1、路網(wǎng)中的空間路徑搜索是地圖服務中的一項基本功能，有別于傳統(tǒng)的最短路徑搜索，基于關鍵詞的最優(yōu)路徑搜索（Keyword-aware Optimal Route Search, KORS）旨在查詢返回一條覆蓋所有用戶指定的查詢關鍵詞、滿足有限的行程預算（行程公里數(shù)），最終有最小花費（行程費用或時間）的路徑。KORS是一種面向基于位置的服務（Location Based Service，LBS）的查詢技術，能夠為用戶個性化的出行提供旅游行程的規(guī)

2、劃。由于KORS具有考察屬性多樣、拓展組合多變、查詢條件受限等特點，實際求解該類問題的真實最優(yōu)解是一類 NP難題，故提出更為有效的查詢處理方法頗具研究挑戰(zhàn)。
　　為減小處理KORS查詢的復雜度，當前最新研究方法采用兩類近似算法以及一類貪婪算法，在優(yōu)化后的解空間下對問題進行近似最優(yōu)求解。然而，這其中依然存在著不足之處，主要表現(xiàn)在：1.近似算法的執(zhí)行效率在大圖及多關鍵詞查詢中存在瓶頸；2.啟發(fā)式算法無法求得能夠滿足所有查詢約束條件的結

3、果。因此本文針對上述兩類問題展開研究，首先對符合 KORS查詢條件的所有可行結果進行分析，發(fā)現(xiàn)KORS的求解本質(zhì)是采用Skyline路徑序列化地構建部分關鍵頂點間的連接。由于現(xiàn)有算法各自采用了較為極端的路徑拓展方式，為權衡查詢處理的效率與精度，本文提出一種新的路徑拓展構建方法：基于關鍵詞的Skyline路徑構建（Keyword-aware Skyline Route Generation, KSRG），以Skyline路徑拓展代替舊有算

4、法中極端的路徑拓展方式，從而使路徑能夠在拓展過程中優(yōu)先滿足對查詢關鍵詞的覆蓋。其次為了有效提升KSRG執(zhí)行的可擴展性，本文進一步設計適用的完全多項式時間近似策略(Fully Polynomial擬Time Approximation Scheme， FPTAS），將原冪指復雜度級下的KSRG求解過程限定在多項式級?；谏鲜隹蚣埽岢鼋扑惴ㄒ詫崿F(xiàn)在大規(guī)模路網(wǎng)圖及多關鍵詞查詢下更為高效通用的KORS查詢處理過程。通過真實路網(wǎng)數(shù)據(jù)集下的實驗