摘要
由于数据爆发增长,数据拥有者不能高效处理客户端发送的查询请求,因此将数据外包给第三方数据发布者,委托第三方数据发布者来管理数据并且执行用户查询.当第三方数据发布者受到黑客攻击或者由于自身计算错误等情况发生时,将导致用户获取错误的查询结果.为了确保用户获得正确、完整且有效的外包空间数据库查询结果,查询验证技术得到了深入研究.此外,反向k最远邻居查询在近年来获得广泛关注.反向k最远邻居查询具有广泛的实际应用.例如,化工厂选址和基于位置的多人角色扮演游戏(如BotFighters).在许多应用中,获得完全正确的查询结果是必要的.如果投建化工厂位置不合适,将会干扰居民和破坏环境.因此,有效和高效的反向k最远邻居查询验证技术对外包数据库是十分有价值的.该文基于已有的反向k最远邻居查询方法和MR-tree验证数据结构,首次提出了两种验证方法:一是IZ-Auth方法,将反向k最远邻居查询验证分解成反向k最远邻居范围验证和该范围内结果的验证两部分.该方法的客户端验证的首要任务是重塑根摘要,判断验证对象是否被篡改或者丢失,然后利用相关定理检验由半空间修剪技术形成的范围,只有完整的范围才能筛选出有效、正确且完整的反向k最远邻居查询结果.二是UC-Auth方法,先重塑根摘要来确保数据来源的可靠性,然后利用外围圆的特性检验验证对象和查询结果.UC-Auth方法的优势在于其不需要计算IZ-Auth方法的范围,这能降低服务器端的计算开销.这两种验证方法是通过优化验证对象数量来降低通信和客户端验证代价.该文利用真实数据集和合成数据集进行了大量的实验,证明了这两种验证算法的有效性和实用性.该文提出的这两种验证算法可以将验证对象缩减至原始数据的5%左右,既降低了通信代价,又提升了客户端验证效率.
As the amount of data explodes rapidly, the data owner cannot handle queries efficiently that clients send. Therefore, the data owner outsources databases to a third-party data publisher and a third-party data publisher is delegated to manage the data and perform user queries. When a third-party data publisher is attacked by a hacker or due to own fallacious calculation, incorrect results will be returned to the user. In order to ensure that users get the correct, complete and valid query results in outsourcing spatial databases, the authentication techniques of queries have been widely explored. Additionally, in recent years, the reverse k furthest neighbor query has caused widespread attention. Given a set of facilities F , a set of users U and a query object q∈F , the reverse k furthest neighbor query retrieves each user u∈U , if q becomes one of the u ’s furthest k facility objects. The reverse k furthest neighbor query can support many practical applications, such as location selection of building chemical factory, and location-based multiplayer role - playing games （such as BotFighters） among others. Specifically, totally correct query results are necessary in a lot of scenarios. For example, if the location of building chemical factory is improper, which will interfere with the life of residents and damage the environment. Therefore, the effective and efficient authentication technique of the reverse k furthest neighbor query is valuable in outsources databases. Based on the existing reverse k furthest neighbor query methods and the authentication data structure of MR-tree, this paper firstly presents two feasible authentication methods of the reverse k furthest neighbor query. The first method （IZ-Auth method） is broken down into two parts： the range verification of the reverse k furthest neighbors query and the validation of the results within that range. The primary task of IZ-Auth in client authentication is to reconstruct the digest of the root node in MR-tree, which determines whether
作者
王海霞
谷峪
于戈
WANG HaiXia;GU Yu;YU Ge(School of Computer Science and Engineering,Northeastern University,Shenyang 110169)
出处
《计算机学报》
EI
CSCD
北大核心
2018年第8期1896-1911,共16页
Chinese Journal of Computers
基金
国家自然科学基金(61472071
61433008)
中央高校基本科研业务费专项资金(N171605001)
辽宁省自然科学基金(2015020018)资助~~
关键词
外包空间数据库
反向k最远邻居查询
半空间修剪技术
验证数据结构
验证对象
outsourcing spatial database
reverse k furthest neighbors
half-space pruning techniques
authentication data structure
verification objects
