外包空间数据库中反向k近邻查询验证  

Authentication of Reverse k Nearest Neighbor Queries for Outsourced Spatial Databases

作　　者：陈子军[1,2] 洪济海[1,2] 刘文远[1,2] 

机构地区：[1]燕山大学信息科学与工程学院,河北秦皇岛066004 [2]河北省计算机虚拟技术与系统集成重点实验室,河北秦皇岛066004

出　　处：《小型微型计算机系统》2013年第8期1819-1824,共6页Journal of Chinese Computer Systems

摘　　要：在外包空间数据库模式下,数据持有者委托第三方数据发布者代替它来管理数据并且执行查询.当发布者受到攻击或者由于自身的不安全性,它可能返回不正确的查询结果给用户.基于已有的反向k近邻(Reverse k Nearest Neighbor,RkNN)查询方法,采用将反向k近邻查询验证转化成k近邻查询验证和范围查询验证的思想,提出一种反向k近邻查询验证的方法,并且设计了相应的算法,用于验证返回给客户端结果的正确性(没有结果点被篡改),有效性(结果点都满足用户的查询要求)和完整性(没有遗漏符合查询要求的结果点).实验验证了算法的有效性和实用性.In outsourced spatial databases model, data owners engage third-party data publishers to manage their data and process que- ries instead of them. As the publishers are attacked or untrusted of themselves, it could return incorrect query results to the user. In this paper, the authors propose a kind of authenticating method and design relevant algorithm for reverse k nearest neighbor query, a- dopted the thought of converting authentication of reverse k nearest neighbor queries into authentication of k nearest neighbor queries and authentication of range queries, based existing algorithm of solving reverse k nearest neighbor query. It can verify user＇s answers are correct（ no answer points are tampered）, effective{ all of answers accord with the user＇s search request} and complete{ no qualif- ying data points are omitted}. Experiments show that our solutions are effective and available.

关 键 词：外包空间数据库 反向k近邻查询 空间数据库 查询验证 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]