| With the popularity of location-based services (LBS) and the abundant usage of smart phones, tablets and other GPS-enabled devices, the necessity of providing efficient, reliable and cost-effective spatial data services has grown rapidly over the past few years. Consequently, outsourcing databases to third party service providers is becoming a common practice for data owners to reduce the cost of managing and maintaining databases in-house but maintaining the same quality-of-service to their clients. Meanwhile, the fast arising trend of Cloud storage and Cloud computing services has provided a flexible and cost-effective platform for hosting data from businesses and individuals, further enabling many location-based applications. Nevertheless, in this new database outsourcing paradigm, how to ensure the integrity of the query results for the clients remains a challenging problem.;To address the query integrity problem, we propose a new framework, named VN-Auth, which allows a client to verify the correctness and completeness of the result set retrieved from the Cloud using spatial neighborhood information derived from the Voronoi diagram of the underlying dataset. VN-Auth handles not only fundamental spatial query types, such as k-nearest-neighbor and range queries, but also more advanced query types like reverse k nearest neighbors, k aggregate nearest neighbors, and spatial skylines. Furthermore, we show that VN-Auth can be extended from the Euclidean space to road networks where objects can only move on pre-defined trajectories, enabling spatial network query integrity. We evaluated VN-Auth based on real-world datasets using mobile devices (Google Droid smart phones with Android OS) as query clients. Compared to the current state-of-the-art approaches (i.e., methods based on Merkle hash trees), our experiments show that VN-Auth produces significantly smaller verification objects and is more computationally efficient, especially for queries with low selectivity. |
