Authentication of Skyline Query over Road Networks

With the increase of location-aware and Internet-capable mobile handset devices, location-based services (LBSs) have experienced an explosive growth in recent years. To scale up services, location-based service providers (LBSPs) outsource data management to third-party cloud service providers (CSPs), which in turn provide data query services to users on behalf of LBSPs. However, the CSPs cannot be trusted, which may return incorrect or incomplete query results to users, intentionally or not. Skyline query is an important kind of query, which asks for the data that is not spatially dominated by any other data. Therefore, enabling users to authenticate skyline query results is essential for outsourced LBSs. In this paper, we propose an authentication solution to support location-based skyline query. By embedding each data with its skyline neighbors in the data's signature, our solution allows users to efficiently verify the soundness and completeness of location-based skyline query results. Through theoretical analysis, we demonstrate the effectiveness of our proposed solution.