A privacy-preserving K-NN query processing algorithm using spatial grid index for outsourced databases

Due to the advancement in cloud computing technology, the research on outsourced databases has been spotlighted. With the development in mobile networks and positioning capabilities, there has been increasing number of users in various types of location-related applications, i.e. location-based services (LBSs) and geo-social network. Therefore, personal or small-size LBS businesses attempt to outsource their spatial database to a service provider, in order to reduce a cost for data storage and management. However, privacy needs to be preserved for spatial databases that are valuable and sensitive against unauthorized accesses. In this paper, we design a spatial database encryption scheme that produces a transformed database from an original database by using network distances among POIs (Points of Interest). Moreover, we propose a k-nearest neighbor (k-NN) query processing algorithm that is efficiently performed on the encrypted database by using a spatial grid index. For this, we revise a pruning technique that incrementally reduces a query search range. Through our performance analysis, it is shown that the proposed algorithm outperforms the existing algorithm in terms of database encryption cost, query processing time and candidate set size.