Efficient Retrieval of Bounded-Cost Informative Routes
- 29 June 2017
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 29 (10) , 2182-2196
Abstract
The widespread location-aware applications produce a vast amount of spatio-textual data that contains both spatial and textual attributes. To make use of this enriched information for users to describe their preferences for travel routes, we propose a Bounded-Cost Informative Route (BCIR) query to retrieve the routes that are the most textually relevant to the user-specified query keywords subject to a travel cost constraint. BCIR query is particularly helpful for tourists and city explorers to plan their travel routes. We will show that BCIR query is an NP-hard problem. To answer BCIR query efficiently, we propose an exact solution with effective pruning techniques and two approximate solutions with performance guarantees. Extensive experiments over real data sets demonstrate that the proposed solutions achieve the expected performance.Keywords
Funding Information
- Hong Kong Polytechnic University (1-ZE26)
- GRF (152196/16E)
- Hong Kong RGC
- NSFC (61332004)
- University’s Support for Application of Major Research Funding
- Hong Kong Polytechnic University (1-BBA1)
- National Natural Science Foundation of China (61373036)
- Program of Shanghai Subject Chief Scientist (15XD1503600)
- Key Projects of Fundamental Research Program of Shanghai Municipal Commission of Science and Technology (14JC1400300)
This publication has 34 references indexed in Scilit:
- An extension of the arc orienteering problem and its application to cycle trip planningTransportation Research Part E: Logistics and Transportation Review, 2014
- Approximate MaxRS in spatial databasesProceedings of the VLDB Endowment, 2013
- Spatial keyword query processingProceedings of the VLDB Endowment, 2013
- Keyword-aware optimal route searchProceedings of the VLDB Endowment, 2012
- A scalable algorithm for maximizing range sum in spatial databasesProceedings of the VLDB Endowment, 2012
- The planning of cycle trips in the province of East FlandersOmega, 2011
- Efficient retrieval of the top-k most relevant spatial web objectsProceedings of the VLDB Endowment, 2009
- Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks2008
- Inverted files for text search enginesACM Computing Surveys, 2006
- On Trip Planning Queries in Spatial Databases2005