Efficient Clue-based Route Search on Road Networks (Extended Abstract)

Bolong Zheng, Han Su, Wen Hua, Kai Zheng, Xiaofang Zhou, Guohui Li

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

Abstract

With the advances in geo-positioning technologies and location-based services, it is nowadays quite common for road networks to have textual contents on the vertices. Previous work on identifying an optimal route that covers a sequence of query keywords has been studied in recent years. However, in many practical scenarios, an optimal route might not always be desirable. Therefore, in this paper, we investigate the problem of clue-based route search (CRS), which allows a user to provide clues on keywords and spatial relationships. First, we propose a greedy algorithm and a dynamic programming algorithm as baselines. To improve efficiency, we develop a branch-And-bound algorithm that prunes unnecessary vertices in query processing. In order to quickly locate candidate, we propose an AB-Tree that stores both the distance and keyword information in tree structure. To further reduce the index size, we construct a PB-Tree by utilizing the virtue of 2-hop label index to pinpoint the candidate. Extensive experiments are conducted and verify the superiority of our algorithms and index structures.

Original languageEnglish
Title of host publicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1783-1784
Number of pages2
ISBN (Electronic)9781538655207
DOIs
Publication statusPublished - 24 Oct 2018
Externally publishedYes
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: 16 Apr 201819 Apr 2018

Publication series

NameProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018

Conference

Conference34th IEEE International Conference on Data Engineering, ICDE 2018
Country/TerritoryFrance
CityParis
Period16/04/1819/04/18

Keywords

  • Clue
  • Point of interest
  • Query processing
  • Spatial keyword queries
  • Travel route serach

ASJC Scopus subject areas

  • Information Systems

Fingerprint

Dive into the research topics of 'Efficient Clue-based Route Search on Road Networks (Extended Abstract)'. Together they form a unique fingerprint.

Cite this