Authenticating spatial skyline queries with low communication overhead

With the emergence of cloud computing and location-based services, owners of spatial data (e.g., collections of geo-tagged photos, social network location check-ins, etc.) have the option to outsource services such as storage and query processing to a cloud service provider. However, providers of such services are not trusted to properly execute queries, so clients must be given assurance that the results are trustworthy. Therefore, authentication of database queries is needed to ensure correctness and completeness of the results provided by the cloud provider. One type of spatial query that is prominent in practice is the spatial skyline query (SSQ), which allows clients to retrieve results according to specific preferences. In this paper, we propose a solution for authenticating spatial skyline queries that focuses on reducing communication cost compared to existing solutions (MR-Trees). By using a flexible partitioning of the domain coupled with an efficient heuristic, we obtain communication costs that are up to three times lower than existing state-of-the-art.