RkNN query integrity with influence zone

• We propose an efficient method to construct the compact verification objects (VO)(VO) at server side.
• Based on the influence zone, two methods (IZ-Auth, AIZ-Auth) are designed to authenticate both monochromatic and bichromatic RkNN queries.
• Our method is the first work to study both types of RkNN authentication, and these methods are extended to verify continuous RkNN query.

With the popularity of location-based service (LBS) and the ever-increasing usage of smart phones and tablet devices, the necessity of outsourcing spatial data has grown rapidly over the past few years. In outsourced spatial databases, the LBS provides query services to the clients on behalf of the data owner. However, the LBS provider is not always trustworthy and it may send incomplete or incorrect query results to the clients. Therefore, ensuring spatial query integrity is critical. In this paper, we propose efficient RkNN query verification techniques which utilize the influence zone to check the integrity of query results. Our methods aim to authenticate both monochromatic and bichromatic RkNN queries results. Specifically, our methods can gain efficient performance on verifying bichromatic RkNN query. Furthermore, our methods can be used to authenticate both snapshot and continuous Rk  NN queries. We also present a detailed theoretical analysis of the size of verification objects (VO)(VO). Extensive experiments on both real and synthetic datasets demonstrate the efficiency of our proposed authenticating methods.