Authentication of Moving Top-k Spatial Keyword Queries

Dingming Wu*, Koon Kau CHOI, Jianliang XU, Christian S. Jensen

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

39 Citations (Scopus)
19 Downloads (Pure)


A moving top-k spatial keyword (MkSK) query, which takes into account a continuously moving query location, enables a mobile client to be continuously aware of the top-k spatial web objects that best match a query with respect to location and text relevance. The increasing mobile use of the web and the proliferation of geo-positioning render it of interest to consider a scenario where spatial keyword search is outsourced to a separate service provider capable at handling the voluminous spatial web objects available from various sources. A key challenge is that the service provider may return inaccurate or incorrect query results (intentionally or not), e.g., due to cost considerations or invasion of hackers. Therefore, it is attractive to be able to authenticate the query results at the client side. Existing authentication techniques are either inefficient or inapplicable for the kind of query we consider. We propose new authentication data structures, the MIR-tree and MIR∗-tree, that enable the authentication of MkSK queries at low computation and communication costs. We design a verification object for authenticating MkSK queries, and we provide algorithms for constructing verification objects and using these for verifying query results. A thorough experimental study on real data shows that the proposed techniques are capable of outperforming two baseline algorithms by orders of magnitude.

Original languageEnglish
Article number6881706
Pages (from-to)922-935
Number of pages14
JournalIEEE Transactions on Knowledge and Data Engineering
Issue number4
Early online date21 Aug 2014
Publication statusPublished - 1 Apr 2015

Scopus Subject Areas

  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

User-Defined Keywords

  • authentication
  • query processing
  • Spatial databases
  • spatial keyword search


Dive into the research topics of 'Authentication of Moving Top-k Spatial Keyword Queries'. Together they form a unique fingerprint.

Cite this