Optimal Sequenced Route Query with POI Preferences

Wenbin Li, Huaijie Zhu*, Wei Liu, Jian Yin, Jianliang Xu

*Corresponding author for this work

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

2 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications
Subtitle of host publication26th International Conference, DASFAA 2021, Taipei, Taiwan, April 11–14, 2021, Proceedings, Part I
EditorsChristian S. Jensen, Ee-Peng Lim, De-Nian Yang, Wang-Chien Lee, Vincent S. Tseng, Vana Kalogeraki, Jen-Wei Huang, Chih-Ya Shen
PublisherSpringer Cham
Number of pages17
ISBN (Electronic)9783030731946
ISBN (Print)9783030731939
Publication statusPublished - 6 Apr 2021
Event26th International Conference on Database Systems for Advanced Applications, DASFAA 2021 - Taipei, Taiwan, Province of China
Duration: 11 Apr 202114 Apr 2021

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349
NameInformation Systems and Applications, incl. Internet/Web, and HCI
NameInternational Conference on Database Systems for Advanced Applications


Conference26th International Conference on Database Systems for Advanced Applications, DASFAA 2021
Country/TerritoryTaiwan, Province of China

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Optimal sequenced route
  • Route planning
  • Spatial database


Dive into the research topics of 'Optimal Sequenced Route Query with POI Preferences'. Together they form a unique fingerprint.

Cite this