外包空间数据库中的反向k最远邻居查询验证技术

• 作者: 于戈 王海霞 谷峪
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 外包空间数据库 反向k最远邻居查询 半空间修剪技术 验证数据结构 验证对象
• 年，卷（期）: 2018,（8）
• 所属期刊栏目: 数据科学与工程
• 页码范围: 1896-1911
• 页数: 16页
• 分类号: TP311
• 字数: 12127字
• 语种: 中文
• DOI: 10.11897/SP.J.1016.2018.01896

摘要

由于数据爆发增长,数据拥有者不能高效处理客户端发送的查询请求,因此将数据外包给第三方数据发布者,委托第三方数据发布者来管理数据并且执行用户查询.当第三方数据发布者受到黑客攻击或者由于自身计算错误等情况发生时,将导致用户获取错误的查询结果.为了确保用户获得正确、完整且有效的外包空间数据库查询结果,查询验证技术得到了深入研究.此外,反向k最远邻居查询在近年来获得广泛关注.反向k最远邻居查询具有广泛的实际应用.例如,化工厂选址和基于位置的多人角色扮演游戏(如BotFighters).在许多应用中,获得完全正确的查询结果是必要的.如果投建化工厂位置不合适,将会干扰居民和破坏环境.因此,有效和高效的反向k最远邻居查询验证技术对外包数据库是十分有价值的.该文基于已有的反向k最远邻居查询方法和MR-tree验证数据结构,首次提出了两种验证方法:一是IZ-Auth方法,将反向k最远邻居查询验证分解成反向k最远邻居范围验证和该范围内结果的验证两部分.该方法的客户端验证的首要任务是重塑根摘要,判断验证对象是否被篡改或者丢失,然后利用相关定理检验由半空间修剪技术形成的范围,只有完整的范围才能筛选出有效、正确且完整的反向k最远邻居查询结果.二是UC-Auth方法,先重塑根摘要来确保数据来源的可靠性,然后利用外围圆的特性检验验证对象和查询结果.UC-Auth方法的优势在于其不需要计算IZ-Auth方法的范围,这能降低服务器端的计算开销.这两种验证方法是通过优化验证对象数量来降低通信和客户端验证代价.该文利用真实数据集和合成数据集进行了大量的实验,证明了这两种验证算法的有效性和实用性,该文提出的这两种验证算法可以将验证对象缩减至原始数据的5％左右,既降低了通信代价,又提升了客户端验证效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	于戈	东北大学计算机科学与工程学院	426	6587	38.0	64.0
2	谷峪	东北大学计算机科学与工程学院	43	456	10.0	20.0
3	王海霞	东北大学计算机科学与工程学院	6	25	2.0	5.0