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

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

Research output: Contribution to book/anthology/report/conference proceedingConference abstract in proceedingResearchpeer-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
Number of pages2
PublisherIEEE
Publication date24 Oct 2018
Pages1783-1784
Article number8509470
ISBN (Print)978-1-5386-5521-4
ISBN (Electronic)978-1-5386-5520-7
DOIs
Publication statusPublished - 24 Oct 2018
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: 16 Apr 201819 Apr 2018

Conference

Conference34th IEEE International Conference on Data Engineering, ICDE 2018
CountryFrance
CityParis
Period16/04/201819/04/2018
SeriesProceedings of the International Conference on Data Engineering
ISSN1063-6382

Fingerprint

Location based services
Query processing
Dynamic programming
Labels
Experiments

Keywords

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

Cite this

Zheng, B., Su, H., Hua, W., Zheng, K., Zhou, X., & Li, G. (2018). Efficient Clue-based Route Search on Road Networks (Extended Abstract). In Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018 (pp. 1783-1784). [8509470] IEEE. Proceedings of the International Conference on Data Engineering https://doi.org/10.1109/ICDE.2018.00249
Zheng, Bolong ; Su, Han ; Hua, Wen ; Zheng, Kai ; Zhou, Xiaofang ; Li, Guohui. / Efficient Clue-based Route Search on Road Networks (Extended Abstract). Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE, 2018. pp. 1783-1784 (Proceedings of the International Conference on Data Engineering).
@inbook{38e9ca8600f7449ba922d3d9a2abacc2,
title = "Efficient Clue-based Route Search on Road Networks (Extended Abstract)",
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.",
keywords = "Clue, Point of interest, Query processing, Spatial keyword queries, Travel route serach",
author = "Bolong Zheng and Han Su and Wen Hua and Kai Zheng and Xiaofang Zhou and Guohui Li",
year = "2018",
month = "10",
day = "24",
doi = "10.1109/ICDE.2018.00249",
language = "English",
isbn = "978-1-5386-5521-4",
series = "Proceedings of the International Conference on Data Engineering",
publisher = "IEEE",
pages = "1783--1784",
booktitle = "Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018",
address = "United States",

}

Zheng, B, Su, H, Hua, W, Zheng, K, Zhou, X & Li, G 2018, Efficient Clue-based Route Search on Road Networks (Extended Abstract). in Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018., 8509470, IEEE, Proceedings of the International Conference on Data Engineering, pp. 1783-1784, 34th IEEE International Conference on Data Engineering, ICDE 2018, Paris, France, 16/04/2018. https://doi.org/10.1109/ICDE.2018.00249

Efficient Clue-based Route Search on Road Networks (Extended Abstract). / Zheng, Bolong; Su, Han; Hua, Wen; Zheng, Kai; Zhou, Xiaofang; Li, Guohui.

Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE, 2018. p. 1783-1784 8509470 (Proceedings of the International Conference on Data Engineering).

Research output: Contribution to book/anthology/report/conference proceedingConference abstract in proceedingResearchpeer-review

TY - ABST

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

AU - Zheng, Bolong

AU - Su, Han

AU - Hua, Wen

AU - Zheng, Kai

AU - Zhou, Xiaofang

AU - Li, Guohui

PY - 2018/10/24

Y1 - 2018/10/24

N2 - 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.

AB - 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.

KW - Clue

KW - Point of interest

KW - Query processing

KW - Spatial keyword queries

KW - Travel route serach

UR - http://www.scopus.com/inward/record.url?scp=85057100567&partnerID=8YFLogxK

U2 - 10.1109/ICDE.2018.00249

DO - 10.1109/ICDE.2018.00249

M3 - Conference abstract in proceeding

SN - 978-1-5386-5521-4

T3 - Proceedings of the International Conference on Data Engineering

SP - 1783

EP - 1784

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

PB - IEEE

ER -

Zheng B, Su H, Hua W, Zheng K, Zhou X, Li G. Efficient Clue-based Route Search on Road Networks (Extended Abstract). In Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE. 2018. p. 1783-1784. 8509470. (Proceedings of the International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2018.00249