Inherent-Cost Aware Collective SpatialKeyword Queries

Harry Kai-Ho Chan, Cheng Long, Raymond Chi-Wing Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

335 Downloads (Pure)


With the proliferation of spatial-textual data such as location-based services and geo-tagged websites, spatial keyword queries become popular in the literature. One example of these queries is the collective spatial keyword query (CoSKQ) which is to find a set of objects in the database such that it covers a given set of query keywords collectively and has the smallest cost. Some existing cost functions were proposed in the literature, which capture different aspects of the distances among the objects in the set and the query. However, we observe that in some applications, each object has an inherent cost (e.g., workers have monetary costs) which are not captured by any of the existing cost functions. Motivated by this, in this paper, we propose a new cost function called the maximum dot size cost which captures both the distances among objects in a set and a query as existing cost functions do and the inherent costs of the objects. We prove that the CoSKQ problem with the new cost function is NP-hard and develop two algorithms for the problem. One is an exact algorithm which is based on a novel search strategy and employs a few pruning techniques and the other is an approximate algorithm which provides a ln q.psi approximation factor, where q.psi denotes the number of query keywords.We conducted extensive experiments based on both real datasets and synthetic datasets, which verified our theoretical results and efficiency of our algorithms.
Original languageEnglish
Title of host publication2017 International Symposium on Spatial and Temporal Databases (SSTD 2017): Proceedings
Number of pages18
Publication statusPublished - 22 Jul 2017

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743


Dive into the research topics of 'Inherent-Cost Aware Collective SpatialKeyword Queries'. Together they form a unique fingerprint.

Cite this