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 contributionpeer-review

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. The experimental results demonstrate that the proposed algorithm significantly outperforms the existing approaches.

Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 26th International Conference, DASFAA 2021, Proceedings
EditorsChristian S. Jensen, Ee-Peng Lim, De-Nian Yang, Wang-Chien Lee, Vincent S. Tseng, Vana Kalogeraki, Jen-Wei Huang, Chih-Ya Shen
PublisherSpringer Science and Business Media Deutschland GmbH
Pages457-473
Number of pages17
ISBN (Print)9783030731939
DOIs
Publication statusPublished - 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 (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12681 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Conference on Database Systems for Advanced Applications, DASFAA 2021
Country/TerritoryTaiwan, Province of China
CityTaipei
Period11/04/2114/04/21

Scopus Subject Areas

  • Theoretical Computer Science
  • Computer Science(all)

User-Defined Keywords

  • Optimal sequenced route
  • Route planning
  • Spatial database

Fingerprint

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

Cite this