TY - JOUR
T1 - Authentication of Moving Top-k Spatial Keyword Queries
AU - Wu, Dingming
AU - CHOI, Koon Kau
AU - XU, Jianliang
AU - Jensen, Christian S.
N1 - Funding information:
This research was supported in part by HK RGC General Research grants (12202414, 210811, and 210510), HKBU Faculty Research grants (FRG/13-14/064 and FRG/12-13/079), and a grant from the Obel Family Foundation.
Publisher copyright:
© 2014 IEEE.
PY - 2015/4/1
Y1 - 2015/4/1
N2 - 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.
AB - 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.
KW - authentication
KW - query processing
KW - Spatial databases
KW - spatial keyword search
UR - http://www.scopus.com/inward/record.url?scp=84924914139&partnerID=8YFLogxK
U2 - 10.1109/TKDE.2014.2350252
DO - 10.1109/TKDE.2014.2350252
M3 - Journal article
AN - SCOPUS:84924914139
SN - 1041-4347
VL - 27
SP - 922
EP - 935
JO - IEEE Transactions on Knowledge and Data Engineering
JF - IEEE Transactions on Knowledge and Data Engineering
IS - 4
M1 - 6881706
ER -