Efficient Clue-Based Route Search on Road Networks

• Published in: IEEE transactions on knowledge and data engineering 2017-09, Vol.29 (9), p.1846-1859
• Main Authors: Zheng, Bolong, Su, Han, Hua, Wen, Zheng, Kai, Zhou, Xiaofang, Li, Guohui
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Approximation algorithms; clue; Context; Dynamic programming; Greedy algorithms; Heuristic algorithms; Indexes; Location based services; point-of-interest; Position (location); Prunes; Queries; Query processing; Roads; Search problems; Spatial keyword queries; travel route search
• ISSN: 1041-4347; 1558-2191
• DOI: 10.1109/TKDE.2017.2703848

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. For example, a personalized route query is issued by providing some clues that describe the spatial context between PoIs along the route, where the result can be far from the optimal one. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-and-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.