TY - GEN
T1 - Optimal Sequenced Route Query with POI Preferences
AU - Li, Wenbin
AU - Zhu, Huaijie
AU - Liu, Wei
AU - Yin, Jian
AU - Xu, Jianliang
N1 - Funding Information:
Acknowledgments. This work is supported by the National Natural Science Foundation of China (61902438, 61902439, U1811264, U19112031), Natural Science Foundation of Guangdong Province under Grant (2019A1515011704, 2019A1515011159), Guangdong Basic and Applied Basic Research Foundation (2019B1515130001), National Science Foundation for Post-Doctoral Scientists of China under Grant (2018M643307, 2019M663237), Young Teacher Training Project of Sun Yat-sen University under Grant (19lgpy214,19lgpy223)and Hong Kong RGC Grant 12200817.
Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021/4/6
Y1 - 2021/4/6
N2 - 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. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.
AB - 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. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.
KW - Optimal sequenced route
KW - Route planning
KW - Spatial database
UR - http://www.scopus.com/inward/record.url?scp=85104753123&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-73194-6_31
DO - 10.1007/978-3-030-73194-6_31
M3 - Conference proceeding
AN - SCOPUS:85104753123
SN - 9783030731939
T3 - Lecture Notes in Computer Science
SP - 457
EP - 473
BT - Database Systems for Advanced Applications
A2 - Jensen, Christian S.
A2 - Lim, Ee-Peng
A2 - Yang, De-Nian
A2 - Lee, Wang-Chien
A2 - Tseng, Vincent S.
A2 - Kalogeraki, Vana
A2 - Huang, Jen-Wei
A2 - Shen, Chih-Ya
PB - Springer Cham
T2 - 26th International Conference on Database Systems for Advanced Applications, DASFAA 2021, held in conjunction with BDQM 2021, GDMA 2021, MLDLDSA 2021, MobiSocial 2021 and MUST 2021
Y2 - 11 April 2021 through 14 April 2021
ER -