Moving spatial keyword queries: Formulation, methods, and analysis

Dingming Wu, Man Lung Yiu, Christian S. Jensen

Research output: Journal article publicationJournal articleAcademic researchpeer-review

33 Citations (Scopus)


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.
Original languageEnglish
Article number7
JournalACM Transactions on Database Systems
Issue number1
Publication statusPublished - 1 Apr 2013


  • Moving query
  • Multiplicatively weighted Voronoi diagram
  • Safe zone
  • Spatial keyword query
  • Voronoi diagram

ASJC Scopus subject areas

  • Information Systems


Dive into the research topics of 'Moving spatial keyword queries: Formulation, methods, and analysis'. Together they form a unique fingerprint.

Cite this