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

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

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

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

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