基于关键词的最优路径查询高效处理方法的研究

发布时间：2018-01-23 21:59

本文关键词： 基于位置的服务基于关键词的最优路径查询 NP难题 Skyline路径路网图算法　出处：《太原理工大学》2017年硕士论文　论文类型：学位论文

【摘要】：路网中的空间路径搜索是地图服务中的一项基本功能,有别于传统的最短路径搜索,基于关键词的最优路径搜索(Keyword-aware Optimal Route Search,KORS)旨在查询返回一条覆盖所有用户指定的查询关键词、满足有限的行程预算(行程公里数),最终有最小花费(行程费用或时间)的路径。KORS是一种面向基于位置的服务(Location Based Service,LBS)的查询技术,能够为用户个性化的出行提供旅游行程的规划。由于KORS具有考察属性多样、拓展组合多变、查询条件受限等特点,实际求解该类问题的真实最优解是一类NP难题,故提出更为有效的查询处理方法颇具研究挑战。为减小处理KORS查询的复杂度,当前最新研究方法采用两类近似算法以及一类贪婪算法,在优化后的解空间下对问题进行近似最优求解。然而,这其中依然存在着不足之处,主要表现在:1.近似算法的执行效率在大图及多关键词查询中存在瓶颈;2.启发式算法无法求得能够满足所有查询约束条件的结果。因此本文针对上述两类问题展开研究,首先对符合KORS查询条件的所有可行结果进行分析,发现KORS的求解本质是采用Skyline路径序列化地构建部分关键顶点间的连接。由于现有算法各自采用了较为极端的路径拓展方式,为权衡查询处理的效率与精度,本文提出一种新的路径拓展构建方法:基于关键词的Skyline路径构建(Keyword-aware Skyline Route Generation,KSRG),以Skyline路径拓展代替旧有算法中极端的路径拓展方式,从而使路径能够在拓展过程中优先满足对查询关键词的覆盖。其次为了有效提升KSRG执行的可扩展性,本文进一步设计适用的完全多项式时间近似策略(Fully Polynomial拟Time Approximation Scheme,FPTAS),将原幂指复杂度级下的KSRG求解过程限定在多项式级。基于上述框架,提出近似算法以实现在大规模路网图及多关键词查询下更为高效通用的KORS查询处理过程。通过真实路网数据集下的实验测试,本文验证了提出方案的有效性:提出算法相对原有算法能够在有限精度损失下有效提升查询执行效率,同时能够在更大规模路网图下具有相对合理的查询开销。
[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.
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP301.6

【参考文献】