Efficient collective spatial keyword query processing on road networks

The collective spatial keyword query (CSKQ), an important variant of spatial keyword queries, aims to find a set of the objects that collectively cover users' queried keywords, and those objects are close to the query location and have small inter-object distances. Existing works only focus on...

Full description

Saved in:
Bibliographic Details
Main Authors: GAO, Yunjun, ZHAO, Jingwen, ZHENG, Baihua, CHEN, Gang
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2016
Subjects:
Online Access:https://ink.library.smu.edu.sg/sis_research/3149
https://ink.library.smu.edu.sg/context/sis_research/article/4149/viewcontent/Efficient_collective_spatial_keyword_query_processing_on_road_networks.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
id sg-smu-ink.sis_research-4149
record_format dspace
spelling sg-smu-ink.sis_research-41492019-04-02T03:13:04Z Efficient collective spatial keyword query processing on road networks GAO, Yunjun ZHAO, Jingwen ZHENG, Baihua CHEN, Gang The collective spatial keyword query (CSKQ), an important variant of spatial keyword queries, aims to find a set of the objects that collectively cover users' queried keywords, and those objects are close to the query location and have small inter-object distances. Existing works only focus on the CSKQ problem in the Euclidean space, although we observe that, in many real-life applications, the closeness of two spatial objects is measured by their road network distance. Thus, existing methods cannot solve the problem of network-based CSKQ efficiently. In this paper, we study the problem of collective spatial keyword query processing on road networks, where the objects are located on a predefined road network. We first prove that this problem is NP-complete, and then we propose two approximate algorithms with provable approximation bounds and one exact algorithm, for supporting CSKQ on road networks efficiently. Extensive experiments using real datasets demonstrate the efficiency and accuracy of our presented algorithms. 2016-02-01T08:00:00Z text application/pdf https://ink.library.smu.edu.sg/sis_research/3149 info:doi/10.1109/TITS.2015.2477837 https://ink.library.smu.edu.sg/context/sis_research/article/4149/viewcontent/Efficient_collective_spatial_keyword_query_processing_on_road_networks.pdf http://creativecommons.org/licenses/by-nc-nd/4.0/ Research Collection School Of Computing and Information Systems eng Institutional Knowledge at Singapore Management University Algorithm collective road network spatial keyword query Databases and Information Systems Transportation
institution Singapore Management University
building SMU Libraries
continent Asia
country Singapore
Singapore
content_provider SMU Libraries
collection InK@SMU
language English
topic Algorithm
collective
road network
spatial keyword query
Databases and Information Systems
Transportation
spellingShingle Algorithm
collective
road network
spatial keyword query
Databases and Information Systems
Transportation
GAO, Yunjun
ZHAO, Jingwen
ZHENG, Baihua
CHEN, Gang
Efficient collective spatial keyword query processing on road networks
description The collective spatial keyword query (CSKQ), an important variant of spatial keyword queries, aims to find a set of the objects that collectively cover users' queried keywords, and those objects are close to the query location and have small inter-object distances. Existing works only focus on the CSKQ problem in the Euclidean space, although we observe that, in many real-life applications, the closeness of two spatial objects is measured by their road network distance. Thus, existing methods cannot solve the problem of network-based CSKQ efficiently. In this paper, we study the problem of collective spatial keyword query processing on road networks, where the objects are located on a predefined road network. We first prove that this problem is NP-complete, and then we propose two approximate algorithms with provable approximation bounds and one exact algorithm, for supporting CSKQ on road networks efficiently. Extensive experiments using real datasets demonstrate the efficiency and accuracy of our presented algorithms.
format text
author GAO, Yunjun
ZHAO, Jingwen
ZHENG, Baihua
CHEN, Gang
author_facet GAO, Yunjun
ZHAO, Jingwen
ZHENG, Baihua
CHEN, Gang
author_sort GAO, Yunjun
title Efficient collective spatial keyword query processing on road networks
title_short Efficient collective spatial keyword query processing on road networks
title_full Efficient collective spatial keyword query processing on road networks
title_fullStr Efficient collective spatial keyword query processing on road networks
title_full_unstemmed Efficient collective spatial keyword query processing on road networks
title_sort efficient collective spatial keyword query processing on road networks
publisher Institutional Knowledge at Singapore Management University
publishDate 2016
url https://ink.library.smu.edu.sg/sis_research/3149
https://ink.library.smu.edu.sg/context/sis_research/article/4149/viewcontent/Efficient_collective_spatial_keyword_query_processing_on_road_networks.pdf
_version_ 1770572867341123584