-
题名外包空间数据库中的反向k最远邻居查询验证技术
- 1
-
-
作者
王海霞
谷峪
于戈
-
机构
东北大学计算机科学与工程学院
-
出处
《计算机学报》
EI
CSCD
北大核心
2018年第8期1896-1911,共16页
-
基金
国家自然科学基金(61472071
61433008)
+1 种基金
中央高校基本科研业务费专项资金(N171605001)
辽宁省自然科学基金(2015020018)资助~~
-
文摘
由于数据爆发增长,数据拥有者不能高效处理客户端发送的查询请求,因此将数据外包给第三方数据发布者,委托第三方数据发布者来管理数据并且执行用户查询.当第三方数据发布者受到黑客攻击或者由于自身计算错误等情况发生时,将导致用户获取错误的查询结果.为了确保用户获得正确、完整且有效的外包空间数据库查询结果,查询验证技术得到了深入研究.此外,反向k最远邻居查询在近年来获得广泛关注.反向k最远邻居查询具有广泛的实际应用.例如,化工厂选址和基于位置的多人角色扮演游戏(如BotFighters).在许多应用中,获得完全正确的查询结果是必要的.如果投建化工厂位置不合适,将会干扰居民和破坏环境.因此,有效和高效的反向k最远邻居查询验证技术对外包数据库是十分有价值的.该文基于已有的反向k最远邻居查询方法和MR-tree验证数据结构,首次提出了两种验证方法:一是IZ-Auth方法,将反向k最远邻居查询验证分解成反向k最远邻居范围验证和该范围内结果的验证两部分.该方法的客户端验证的首要任务是重塑根摘要,判断验证对象是否被篡改或者丢失,然后利用相关定理检验由半空间修剪技术形成的范围,只有完整的范围才能筛选出有效、正确且完整的反向k最远邻居查询结果.二是UC-Auth方法,先重塑根摘要来确保数据来源的可靠性,然后利用外围圆的特性检验验证对象和查询结果.UC-Auth方法的优势在于其不需要计算IZ-Auth方法的范围,这能降低服务器端的计算开销.这两种验证方法是通过优化验证对象数量来降低通信和客户端验证代价.该文利用真实数据集和合成数据集进行了大量的实验,证明了这两种验证算法的有效性和实用性.该文提出的这两种验证算法可以将验证对象缩减至原始数据的5%左右,既降低了通信代价,又提升了客户端验证效率.
-
关键词
外包空间数据库
反向k最远邻居查询
半空间修剪技术
验证数据结构
验证对象
-
Keywords
outsourcing spatial database
reverse k furthest neighbors
half-space pruning techniques
authentication data structure
verification objects
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名空间数据库中反最远邻查询方法
被引量：2
- 2
-
-
作者
邓成玉
彭川
王宝文
刘文远
吴晓光
-
机构
燕山大学信息科学与工程学院
河北省计算机虚拟技术与系统集成重点实验室
郑州大学信息工程学院
-
出处
《燕山大学学报》
CAS
2013年第5期412-419,共8页
-
文摘
在欧式空间下反最远邻查询算法的研究已取得了很多成果,但反最远邻查询问题还未得到有效解决。本文提出一种反最远邻查询算法,有效地解决了反最远邻查询问题,查询算法采用了过滤-提炼的解决模型。在过滤阶段,提出了反远中垂线裁剪方法。该裁剪法是通过做中垂线来过滤不是查询点的反最远邻的点。在提炼阶段,提出了反远范围查询提炼方法。该提炼方法是通过判断对象点是否在设定的范围外来验证该点是否是查询点的反最远邻。最后通过实验验证了所提算法的有效性。
-
关键词
空间数据库
反最远邻
最远邻
-
Keywords
spatial database
reverse k furthest neighbor
k furthest neighbor
furthest neighbor
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名路网上的单色和双色反k最远邻查询
被引量：3
- 3
-
-
作者
王宝文
彭川
陈子军
刘文远
-
机构
燕山大学信息科学与工程学院
河北省计算机虚拟技术与系统集成重点实验室
-
出处
《计算机工程与设计》
CSCD
北大核心
2012年第8期3099-3104,共6页
-
文摘
传统的路网上的反最远邻查询是直接找出查询点的反最远邻,这种方法不但效率不高,而且需要大量内存资源进行预计算。为了更有效地解决基于路网的单色和双色反k最远邻查询问题,提高反k最远邻查询的效率,提出了从反最近邻的角度来分析反最远邻查询问题,把反最远邻查询转化为反最近邻问题。根据这一理论,提出了一种有效的基于路网的单色和双色的反k最远邻查询算法。通过实验与实验分析表明,该方法具有良好的实用价值。
-
关键词
反最远邻
最远邻
单色查询
双色查询
路网
-
Keywords
RFN
k furthest neighbor
monochromatic reverse k furthest neighbor
bichromatic reverse k furthest neighbor
road networks
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
