Efficient Processing of Spatial Group Keyword Queries

Xin Cao, Gao Cong, Tao Guo, Christian S. Jensen, Beng Chin Ooi

Research output: Contribution to journalArticlepeer-review

51 Citations (Scopus)


With the proliferation of geo-positioning and geo-tagging techniques, spatio-textual objects that possess both a geographical location and a textual description are gaining in prevalence, and spatial keyword queries that exploit both location and textual description are gaining in prominence. However, the queries studied so far generally focus on finding individual objects that each satisfy a query rather than finding groups of objects where the objects in a group together satisfy a query.

We define the problem of retrieving a group of spatio-textual objects such that the group's keywords cover the query's keywords and such that the objects are nearest to the query location and have the smallest inter-object distances. Specifically, we study three instantiations of this problem, all of which are NP-hard. We devise exact solutions as well as approximate solutions with provable approximation bounds to the problems. In addition, we solve the problems of retrieving top-k groups of three instantiations, and study a weighted version of the problem that incorporates object weights. We present empirical studies that offer insight into the efficiency of the solutions, as well as the accuracy of the approximate solutions.
Original languageEnglish
Article number13
Pages (from-to)1-48
Number of pages48
JournalACM Transactions on Database Systems
Issue number2
Publication statusPublished - Jun 2015


Dive into the research topics of 'Efficient Processing of Spatial Group Keyword Queries'. Together they form a unique fingerprint.

Cite this