Efficient Processing of Spatial Group Keyword Queries
Authors:
Open Access
- 30 June 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Database Systems
- Vol. 40 (2) , 1-48
Abstract
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.Keywords
Funding Information
- Seventh Framework Programme (264994)
- Obel Family Foundation
- Ministry of Education - Singapore (ARC30/12)
This publication has 37 references indexed in Scilit:
- Big data: the driver for innovation in databasesNational Science Review, 2014
- A framework for efficient spatial web object retrievalThe VLDB Journal, 2012
- Spatial Keyword Querying2012
- Hybrid Indexing and Seamless Ranking of Spatial and Textual Features of Web Documents2010
- The optimal sequenced route queryThe VLDB Journal, 2007
- Inverted files for text search enginesACM Computing Surveys, 2006
- On Trip Planning Queries in Spatial Databases2005
- Spatio-textual Indexing for Geographical Search on the Web2005
- A study of smoothing methods for language models applied to information retrievalACM Transactions on Information Systems, 2004
- An optimal algorithm for constructing the weighted voronoi diagram in the planePattern Recognition, 1984