Collective spatial keyword querying

TLDR

The rise of geo‑positioned, geo‑tagged web objects has made spatial keyword queries that combine location and text increasingly common, yet existing work focuses on single objects rather than groups that collectively satisfy a query. This paper formulates the problem of selecting a group of spatial web objects whose combined keywords cover a query while the objects are close to the query location and to each other. Two NP‑complete variants of the problem are examined, and both exact algorithms and approximation algorithms with provable bounds are developed. Experiments demonstrate that the proposed algorithms are efficient and achieve high accuracy in retrieving such groups.

Abstract

With the proliferation of geo-positioning and geo-tagging, spatial web 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 collectively satisfy a query. We define the problem of retrieving a group of spatial web objects such that the group's keywords cover the query's keywords and such that objects are nearest to the query location and have the lowest inter-object distances. Specifically, we study two variants of this problem, both of which are NP-complete. We devise exact solutions as well as approximate solutions with provable approximation bounds to the problems. We present empirical studies that offer insight into the efficiency and accuracy of the solutions.