We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Top k Optimal Sequenced Route Query with POI Preferences.
- Authors
Zhu, Huaijie; Li, Wenbin; Liu, Wei; Yin, Jian; Xu, Jianliang
- Abstract
The optimal sequenced route (OSR) query, as a popular problem in route planning for smart cities, searches for a minimum-distance route passing through several POIs in a specific order from a starting position. In reality, POIs are usually rated, which helps users in making decisions. Existing OSR queries neglect the fact that the POIs in the same category could have different scores, which may affect users' route choices. In this paper, we study a novel variant of OSR query, namely Rating Constrained Optimal Sequenced Route query (RCOSR), in which the rating score of each POI in the optimal sequenced route should exceed the query threshold. To efficiently process RCOSR queries, we first extend the existing TD-OSR algorithm to propose a baseline method, called MTDOSR. To tackle the shortcomings of MTDOSR, we try to design a new RCOSR algorithm, namely Optimal Subroute Expansion (OSE) Algorithm. To enhance the OSE algorithm, we propose a Reference Node Inverted Index (RNII) to accelerate the distance computation of POI pairs in OSE and quickly retrieve the POIs of each category. To make full use of the OSE and RNII, we further propose a new efficient RCOSR algorithm, called Recurrent Optimal Subroute Expansion (ROSE), which recurrently utilizes OSE to compute the current optimal route as the guiding path and update the distance of POI pairs to guide the expansion. Then, we extend our techniques to handle a variation of RCOSR query, namely RCkOSR query. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.
- Subjects
ROUTE choice; SMART cities; URBAN planning; DECISION making
- Publication
Data Science & Engineering, 2022, Vol 7, Issue 1, p3
- ISSN
2364-1185
- Publication type
Article
- DOI
10.1007/s41019-022-00177-5