本文關(guān)鍵詞： 基于位置的服務(wù) 基于關(guān)鍵詞的最優(yōu)路徑查詢 NP難題 Skyline路徑 路網(wǎng)圖 算法　出處：《太原理工大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：路網(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ī)劃。由于KORS具有考察屬性多樣、拓展組合多變、查詢條件受限等特點(diǎn),實(shí)際求解該類問(wèn)題的真實(shí)最優(yōu)解是一類NP難題,故提出更為有效的查詢處理方法頗具研究挑戰(zhàn)。為減小處理KORS查詢的復(fù)雜度,當(dāng)前最新研究方法采用兩類近似算法以及一類貪婪算法,在優(yōu)化后的解空間下對(duì)問(wèn)題進(jìn)行近似最優(yōu)求解。然而,這其中依然存在著不足之處,主要表現(xiàn)在:1.近似算法的執(zhí)行效率在大圖及多關(guān)鍵詞查詢中存在瓶頸;2.啟發(fā)式算法無(wú)法求得能夠滿足所有查詢約束條件的結(jié)果。因此本文針對(duì)上述兩類問(wèn)題展開(kāi)研究,首先對(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路徑拓展代替舊有算法中極端的路徑拓展方式,從而使路徑能夠在拓展過(guò)程中優(yōu)先滿足對(duì)查詢關(guān)鍵詞的覆蓋。其次為了有效提升KSRG執(zhí)行的可擴(kuò)展性,本文進(jìn)一步設(shè)計(jì)適用的完全多項(xiàng)式時(shí)間近似策略(Fully Polynomial擬Time Approximation Scheme,FPTAS),將原冪指復(fù)雜度級(jí)下的KSRG求解過(guò)程限定在多項(xiàng)式級(jí)�；谏鲜隹蚣�,提出近似算法以實(shí)現(xiàn)在大規(guī)模路網(wǎng)圖及多關(guān)鍵詞查詢下更為高效通用的KORS查詢處理過(guò)程。通過(guò)真實(shí)路網(wǎng)數(shù)據(jù)集下的實(shí)驗(yàn)測(cè)試,本文驗(yàn)證了提出方案的有效性:提出算法相對(duì)原有算法能夠在有限精度損失下有效提升查詢執(zhí)行效率,同時(shí)能夠在更大規(guī)模路網(wǎng)圖下具有相對(duì)合理的查詢開(kāi)銷。
[Abstract]:Spatial path search in road network is a basic function in map service, which is different from traditional shortest path search. Keyword based optimal path search for Keyword-aware Optimal Route Search. KORS is designed to return a query keyword that covers all users and meets a limited travel budget (km). Ultimately, paths with minimal cost (travel cost or time). Kors is a location-oriented service location Based Service LBS-based query technology. It can provide travel planning for users' personalized travel. Because KORS has the characteristics of diverse inspection attributes, changeable expansion and combination, limited query conditions and so on. It is a kind of NP-hard problem to solve the real optimal solution of this kind of problem in practice, so it is a challenge to propose a more effective query processing method, in order to reduce the complexity of processing KORS query. At present, two kinds of approximate algorithms and a class of greedy algorithms are used to solve the problem in the optimized solution space. However, there are still some shortcomings. The efficiency of the approximate algorithm is bottleneck in large graph and multi-keyword query. 2. The heuristic algorithm can not obtain the results that can satisfy all the query constraints. So this paper studies the above two kinds of problems. Firstly, we analyze all the feasible results that meet the KORS query conditions. It is found that the essence of solving KORS is to serialize the connection between some key vertices by using Skyline path. In order to balance the efficiency and accuracy of query processing. In this paper, we propose a new method of path extension construction: Skyline path construction based on keywords (. Keyword-aware Skyline Route Generation. Skyline path extension is used to replace the extreme path expansion in the old algorithms. In order to improve the scalability of KSRG execution, the path can first satisfy the coverage of query keywords in the process of expansion. In this paper, we further design a perfect polynomial time approximation strategy, full Polynomial quasi Time Approximation Scheme. Based on the above framework, the KSRG solution at the complexity level of the original power exponent is limited to polynomial order. An approximate algorithm is proposed to realize a more efficient and general KORS query processing process under large-scale road map and multi-keyword query. The experimental test is carried out under the real road network data set. This paper verifies the effectiveness of the proposed scheme: compared with the original algorithm, the proposed algorithm can effectively improve the query execution efficiency under the limited precision loss, and it can also have a relatively reasonable query cost under the larger road network map.
【學(xué)位授予單位】：太原理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TP301.6

【參考文獻(xiàn)】

相關(guān)期刊論文 前3條

1 劉喜平;萬(wàn)常選;劉德喜;廖國(guó)瓊;;空間關(guān)鍵詞搜索研究綜述[J];軟件學(xué)報(bào);2016年02期

2 鮑金玲;楊曉春;王斌;王佳英;;一種支持約束關(guān)系的高效的行程規(guī)劃算法[J];小型微型計(jì)算機(jī)系統(tǒng);2013年12期

3 宋曉宇;許鴻斐;孫煥良;劉俊嶺;;基于簽到數(shù)據(jù)的短時(shí)間體驗(yàn)式路線搜索[J];計(jì)算機(jī)學(xué)報(bào);2013年08期

相關(guān)碩士學(xué)位論文 前1條

1 黃櫻;基于劃分的雙向過(guò)濾—驗(yàn)證字符串相似連接[D];太原理工大學(xué);2016年

，

本文編號(hào)：1458334