Generalizing the Optimality of Multi-Step k-NN Query Processing with RASP Data Perturbation in the Cloud

摘要

With the wide deployment of public cloud computing infrastructures, using clouds to host data query services has become an appealing solution for the advantages on scalability and cost-saving. However, some data might be sensitive that the data owner does not want to move to the cloud unless the data confidentiality and query privacy are guaranteed. Due to diversity of applications, the database services in cloud must also support storage of multidimensional data. On the other hand, a secured query service should still provide efficient query processing and significantly reduce the in-house workload to fully realize the benefits of cloud computing. The base paper propose the RASP data perturbation method to provide secure and efficient range query and kNN query services for protected data in the cloud [1]. The kNN-R algorithm is designed to work with the RASP range query algorithm to process the kNN queries. But kNN-R algorithm will not work effectively in high dimensional data (complex objects such as spatial, temporal and multimedia data). In this paper, we integrate kNN-R algorithm and the traditional concept of R-optimality and propose a new multi-step RI kNN-R search algorithm that utilizes lower- and upper bounding distance information (Ilu) in the filter step.In order to reduce the number of candidates returned from the filter step which then have to be exactly evaluated in the refinement step is fundamental for the efficiency of the query process.