Moving Spatial Keyword Queries: Formulation, Methods, and Analysis

Publikation: Bidrag til tidsskrift/Konferencebidrag i tidsskrift /Bidrag til avisTidsskriftartikelForskningpeer review

  • Dingming Wu, Hong Kong Baptist University, Hong Kong
  • Man Lung Yiu, Hong Kong Polytechnic University, Hong Kong
  • Christian S. Jensen, Danmark
Web users and content are increasingly being geo-positioned. This development gives prominence to spatial keyword queries, which involve both the locations and textual descriptions of content. We study the efficient processing of continuously moving top-k spatial keyword (MkSK) queries over spatial text data. State-of-the-art solutions for moving queries employ safe zones that guarantee the validity of reported results as long as the user remains within the safe zone associated with a result. However, existing safe-zone methods focus solely on spatial locations and ignore text relevancy.

We propose two algorithms for computing safe zones that guarantee correct results at any time and that aim to optimize the server-side computation as well as the communication between the server and the client. We exploit tight and conservative approximations of safe zones and aggressive computational space pruning. We present techniques that aim to compute the next safe zone efficiently, and we present two types of conservative safe zones that aim to reduce the communication cost. Empirical studies with real data suggest that the proposals are efficient.

To understand the effectiveness of the proposed safe zones, we study analytically the expected area of a safe zone, which indicates on average for how long a safe zone remains valid, and we study the expected number of influence objects needed to define a safe zone, which gives an estimate of the average communication cost. The analytical modeling is validated through empirical studies.
OriginalsprogEngelsk
Artikelnummer7
TidsskriftA C M Transactions on Database Systems
Vol/bind38
Nummer1
Antal sider47
ISSN0362-5915
DOI
StatusUdgivet - 2013

Se relationer på Aarhus Universitet Citationsformater

ID: 52749354