Efficient Processing of Spatial Group Keyword Queries
Efficient Processing of Spatial Group Keyword Queries
复制标题
DOI：
10.1145/2772600
复制
发表时间：
2015-06
期刊：
影响因子：
--
通讯作者：
Xin Cao;G. Cong;Tao Guo;Christian S. Jensen;B. Ooi
中科院分区：
文献类型：
--
作者：
Xin Cao;G. Cong;Tao Guo;Christian S. Jensen;B. Ooi
随着地理定位和地理标记技术的发展，同时具有地理位置和文本描述的空间文本对象越来越流行，并且利用位置和文本描述的空间关键字查询越来越突出。然而，到目前为止研究的查询通常集中在寻找每个满足查询的单个对象，而不是寻找对象组，其中组中的对象一起满足查询。我们定义的问题，检索一组的空间文本对象，使该组的关键字覆盖查询的关键字，使对象是最近的查询位置，并具有最小的对象间的距离。具体来说，我们研究了这个问题的三个实例，所有这些都是NP难的。我们设计精确的解决方案，以及近似的解决方案与可证明的近似界的问题。此外，我们解决了检索前k组的三个实例的问题，并研究了加权版本的问题，将对象的权重。我们提出的实证研究，提供洞察的解决方案的效率，以及近似解决方案的准确性。
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.