Keyword-aware optimal route search

Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from his hotel is within...

Full description

Bibliographic Details
Main Authors: Cao, Xin, Chen, Lisi, Cong, Gao, Xiao, Xiaokui
Other Authors: School of Computer Engineering
Format: Journal Article
Language:English
Published: 2014
Subjects:
Online Access:https://hdl.handle.net/10356/102238
http://hdl.handle.net/10220/18930
http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350234&dl=ACM&coll=DL
_version_ 1826120352765313024
author Cao, Xin
Chen, Lisi
Cong, Gao
Xiao, Xiaokui
author2 School of Computer Engineering
author_facet School of Computer Engineering
Cao, Xin
Chen, Lisi
Cong, Gao
Xiao, Xiaokui
author_sort Cao, Xin
collection NTU
description Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from his hotel is within 4 hours." However, none of the algorithms in the existing work on route planning can be used to answer such queries. Motivated by this, we define the problem of keyword-aware optimal route query, denoted by KOR, which is to find an optimal route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We devise an approximation algorithm OSScaling with provable approximation bounds. Based on this algorithm, another more efficient approximation algorithm BucketBound is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently, while the BucketBound and Greedy algorithms run faster. The empirical studies also offer insight into the accuracy of the proposed algorithms.
first_indexed 2024-10-01T05:14:47Z
format Journal Article
id ntu-10356/102238
institution Nanyang Technological University
language English
last_indexed 2024-10-01T05:14:47Z
publishDate 2014
record_format dspace
spelling ntu-10356/1022382020-05-28T07:18:03Z Keyword-aware optimal route search Cao, Xin Chen, Lisi Cong, Gao Xiao, Xiaokui School of Computer Engineering Computer Science Engineering Identifying a preferable route is an important problem that finds applications in map services. When a user plans a trip within a city, the user may want to find "a most popular route such that it passes by shopping mall, restaurant, and pub, and the travel time to and from his hotel is within 4 hours." However, none of the algorithms in the existing work on route planning can be used to answer such queries. Motivated by this, we define the problem of keyword-aware optimal route query, denoted by KOR, which is to find an optimal route such that it covers a set of user-specified keywords, a specified budget constraint is satisfied, and an objective score of the route is optimal. The problem of answering KOR queries is NP-hard. We devise an approximation algorithm OSScaling with provable approximation bounds. Based on this algorithm, another more efficient approximation algorithm BucketBound is proposed. We also design a greedy approximation algorithm. Results of empirical studies show that all the proposed algorithms are capable of answering KOR queries efficiently, while the BucketBound and Greedy algorithms run faster. The empirical studies also offer insight into the accuracy of the proposed algorithms. 2014-03-20T09:03:23Z 2019-12-06T20:52:06Z 2014-03-20T09:03:23Z 2019-12-06T20:52:06Z 2012 2012 Journal Article Cao, X., Chen, L., Cong, G., & Xiao, X. (2012). Keyword-aware optimal route search. Proceedings of the VLDB Endowment, 5(11), 1136-1147. https://hdl.handle.net/10356/102238 http://hdl.handle.net/10220/18930 http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350234&dl=ACM&coll=DL en Proceedings of the VLDB Endowment © 2012 VLDB endowment.
spellingShingle Computer Science Engineering
Cao, Xin
Chen, Lisi
Cong, Gao
Xiao, Xiaokui
Keyword-aware optimal route search
title Keyword-aware optimal route search
title_full Keyword-aware optimal route search
title_fullStr Keyword-aware optimal route search
title_full_unstemmed Keyword-aware optimal route search
title_short Keyword-aware optimal route search
title_sort keyword aware optimal route search
topic Computer Science Engineering
url https://hdl.handle.net/10356/102238
http://hdl.handle.net/10220/18930
http://dl.acm.org.ezlibproxy1.ntu.edu.sg/citation.cfm?id=2350234&dl=ACM&coll=DL
work_keys_str_mv AT caoxin keywordawareoptimalroutesearch
AT chenlisi keywordawareoptimalroutesearch
AT conggao keywordawareoptimalroutesearch
AT xiaoxiaokui keywordawareoptimalroutesearch