Authentication of Moving Top-k Spatial Keyword Queries
Authentication of Moving Top-k Spatial Keyword Queries
复制标题
DOI：
10.1109/tkde.2014.2350252
复制
发表时间：
2015-04
影响因子：
8.9
通讯作者：
Dingming Wu;Byron Choi;Jianliang Xu;Christian S. Jensen
中科院分区：
文献类型：
--
作者：
Dingming Wu;Byron Choi;Jianliang Xu;Christian S. Jensen
移动前 k 个空间关键字 (MkSK) 查询考虑了连续移动的查询位置，使移动客户端能够持续了解在位置和文本相关性方面与查询最匹配的前 k 个空间 Web 对象。网络的移动使用的增加和地理定位的激增使得考虑将空间关键字搜索外包给能够处理可从各种来源获得的大量空间网络对象的单独服务提供商的场景变得有趣。一个关键的挑战是服务提供商可能会（有意或无意）返回不准确或不正确的查询结果，例如由于成本考虑或黑客入侵。因此，能够在客户端验证查询结果是很有吸引力的。现有的身份验证技术要么效率低下，要么不适用于我们考虑的查询类型。我们提出了新的身份验证数据结构，即 MIR 树和 MIR* 树，它们能够以较低的计算和通信成本对 MkSK 查询进行身份验证。我们设计了一个用于验证 MkSK 查询的验证对象，并提供了用于构造验证对象并使用它们来验证查询结果的算法。对真实数据的彻底实验研究表明，所提出的技术能够比两种基线算法好几个数量级。
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.