A Keyword-Aware Optimal Route Query Algorithm on Large-Scale Road Networks

摘要

Mobile users prefer to choose personalized travel routes using their mobile terminals. Keyword-aware Optimal Route Query (KORQ) is proposed to meet users' need because it not only considering the length of the route, but also considering the cost of the route and the points of interest covered by the route. As the number of points of interest in road networks increases sharply, the time and space complexity for preprocessing and route expansion rises dramatically, and the state of the art algorithms are not scalable. To address these issues, we propose an algorithm called KORAL, short for Keyword-aware Optimal Route Query Algorithm on Large-scale Road Networks. To reduce the overhead of preprocessing, KORAL partitions the road network into subgraphs, and stores only the information about the routes between subgraphs in preprocessing stages. In the rout expansion stage, KORAL uses a strategy called minimum budget pruning to prune infeasible vertices, which greatly speed up the route expansion. Experiments against 3 datasets of New York road network in a server with 16G RAM show that KORAL is scalable and breaks the limitation that the road network cannot exceed 100K vertices.