Efficient clue-based route search on road networks

Zheng, Bolong, Su, Han, Hua, Wen, Zheng, Kai, Zhou, Xiaofang and Li, Guohui (2017) Efficient clue-based route search on road networks. IEEE Transactions On Knowledge and Data Engineering, 29 9: 1846-1859. doi:10.1109/TKDE.2017.2703848

Author Zheng, Bolong
Su, Han
Hua, Wen
Zheng, Kai
Zhou, Xiaofang
Li, Guohui
Title Efficient clue-based route search on road networks
Journal name IEEE Transactions On Knowledge and Data Engineering   Check publisher's open access policy
ISSN 1041-4347
Publication date 2017-09-01
Sub-type Article (original research)
DOI 10.1109/TKDE.2017.2703848
Open Access Status Not yet assessed
Volume 29
Issue 9
Start page 1846
End page 1859
Total pages 14
Place of publication Piscataway, NJ, United States
Publisher Institute of Electrical and Electronics Engineers
Language eng
Subject 1710 Information Systems
1706 Computer Science Applications
1703 Computational Theory and Mathematics
Abstract 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 (sf 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.
Keyword Spatial keyword queries
Travel route search
Query processing
Q-Index Code C1
Q-Index Status Provisional Code
Grant ID LP130100164
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: HERDC Pre-Audit
School of Information Technology and Electrical Engineering Publications
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in Thomson Reuters Web of Science Article
Scopus Citation Count Cited 1 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Mon, 28 Aug 2017, 01:01:01 EST by Web Cron on behalf of Learning and Research Services (UQ Library)