Research On Authentication Of Reverse K Nearest Neighbor Query For Outsourced Spatial Databases

In outsourced spatial databases model, data owners engage third-party data publishersto manage their data and process query instead of them. As the publishers are attacked oruntrusted of themselves, it may return incorrect query results to the user. In this paper, theauthor proposes a kind of authenticating method for reverse k nearest neighbor query,including authentication of static reverse k nearest neighbor query and continuousauthentication of reverse k nearest neighbor query.Firstly, for the problem of authentication of static reverse k nearest neighbor query,the author proposes a kind of authenticating method and design relevant algorithm forstatic reverse k nearest neighbor query, the algorithm is the thought of convertingauthentication of static reverse k nearest neighbor query into authentication of k nearestneighbor query and authentication of range query, based on existing algorithm of solvingreverse k nearest neighbor query. It can verify user’s answers are correct (no answer pointsare tampered), effective (all of answers accord with the user’s search request) andcomplete (no qualifying data points are omitted). We analyse theoretically the method ofauthentication of query can satisfy the character of authentication of query(the correctness,the effectiveness and the completeness).Secondly, the author puts forward the method that can solve continuousauthentication of reverse k nearest neighbor query. By using the method, we can convertcontinuous authentication of reverse k nearest neighbor query to continuous authenticationof range query. In order to solve continuous authentication of range query, the authorimproves the existing authenticated data structure (ADS), then it is suitable for continuousauthentication of range query, further the author puts forward the new ADS that can solvecontinuous authentication of range query better. By using the method and the ADS, weverify the correctness, the effectiveness, the completeness and the real-time of everyquery.Finally, the above mentioned two methods of authentication of query use simulationdata set to test, the test results show our solutions is available.