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

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

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceabstrakt i proceedingForskningpeer review

Resumé

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.
OriginalsprogEngelsk
TitelProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
Antal sider2
ForlagIEEE
Publikationsdato24 okt. 2018
Sider1783-1784
Artikelnummer8509470
ISBN (Trykt)978-1-5386-5521-4
ISBN (Elektronisk)978-1-5386-5520-7
DOI
StatusUdgivet - 24 okt. 2018
Begivenhed34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, Frankrig
Varighed: 16 apr. 201819 apr. 2018

Konference

Konference34th IEEE International Conference on Data Engineering, ICDE 2018
LandFrankrig
ByParis
Periode16/04/201819/04/2018
NavnProceedings of the International Conference on Data Engineering
ISSN1063-6382

Fingerprint

Location based services
Query processing
Dynamic programming
Labels
Experiments

Citer dette

Zheng, B., Su, H., Hua, W., Zheng, K., Zhou, X., & Li, G. (2018). Efficient Clue-based Route Search on Road Networks (Extended Abstract). I Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018 (s. 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. s. 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). i Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018., 8509470, IEEE, Proceedings of the International Conference on Data Engineering, s. 1783-1784, Paris, Frankrig, 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. s. 1783-1784 8509470 (Proceedings of the International Conference on Data Engineering).

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceabstrakt i proceedingForskningpeer 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). I Proceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018. IEEE. 2018. s. 1783-1784. 8509470. (Proceedings of the International Conference on Data Engineering). https://doi.org/10.1109/ICDE.2018.00249