摘要:游客倾向于采用个性化的旅游路线，规划这样的路线需要综合考量路径长度、路径开销和路径覆盖的兴趣点.关键词覆盖最优路径查询（KOR）就是用于规划这样的路线的一类查询，其处理过程通常包括预处理和路径拓展.由于路网图规模的不断扩大，现有算法预处理所需内存开销急剧上升，由于内存不足，导致较大规模的路网不能处理；路径拓展搜索空间快速膨胀，应用场景可扩展性与查询实时性难以保证.针对这些问题，提出一种大规模路网图下关键词覆盖最优路径查询算法KORL.KORL在预处理阶段将路网划分为若干子图，仅保存子图内路径和子图之间路径的信息，以减小预处理所需内存.在路径拓展阶段，综合运用最小代价剪枝、近似支配剪枝、全局优先拓展和关键词顶点拓展等策略对现有算法进行优化，以高效地搜索近似最优解.采用美国各地区的路网图，在16G内存环境下进行实验，突破了现有算法只能处理顶点数不超过25K路网图的限制.实验结果表明，KORL算法具有良好的可扩展性.



Abstract:Visitors tend to choose personalized travel routes. Planning such a route requires a comprehensive consideration of the length and cost of the route, and the points of interest covered by the route. Keyword-aware optimal route query (KOR) is a typical query for this purpose. Processing a KOR consists of preprocessing and route expansion. With the scale of maps of road networks continues to expand, the overhead for preprocessing and the search space for route expansion increase rapidly. The scalability and the real-time responsiveness are hard to guarantee. To alleviate these pain points, an algorithm called keyword-aware optimal route query algorithm on large-scale road networks or KORL is proposed. In the preprocessing stage, KORL reduces memory requirements by partitioning the road network into subgraphs and stores only information about the routes inside and between subgraphs. In the route expansion stage, KORL combines four strategies, namely minimum cost pruning, approximately dominance pruning, global priority expansion, and keyword vertex expansion to efficiently search the approximate optimal solution. The road networks of various regions in the United States are used as experimental datasets and the experiments are run by the computer with 16 G memory. The limitation that existing algorithms can only handle the road network with the number of vertexes less than 25K is broken. Experiments show that KORL has sound scalability.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5808