Optimal assignment as a location based service in outsourced databases

Abstract

With the growth of mobile devices that have positioning capabilities, location based services promises great opportunities. Moreover to this, service providers would like to focus on their services instead of managing servers and they require exibility to expand or shrink their infrastructure according to the market. These are the two strong drives for outsourced spatial databases. In the literature, several di erent queries such as nearest neighbor, K-nearest neighbor, proximity and privacy preserving techniques have been studied in outsourced spatial databases. In this thesis, the capacity and coverage constrained assignment query is adapted to the outsourced databases. Unlike the other assignment queries in fully connected graphs, we focused on sparse graphs which is more realistic for location based services. A novel spatial transformation strategy (square spiral encoding) is introduced to achieve privacy and performance requirements with approximate results. Approximate solution provides a trade o between result accuracy, location privacy and computation cost . For exact results, we also introduce a new method to calculate distance over encrypted spatial data. In the experiments, we compared the both methods and investigate their performance and costs.