Spatial Outsourcing for Location-Based Services

The embedding of positioning capabilities in mobile devices and the emergence of location-based applications have created novel opportunities for utilizing several types of multidimensional data through spatial outsourcing. In this setting, a Data Owner (DO) delegates its data management tasks to a Location-Based Service (LBS) that processes queries originating from several clients/ subscribers. Because the LBS is not the real owner of the data, it must prove (to each client) the correctness of query output using an authenticated structure signed by the DO. Currently there is very narrow selection of multi-dimensional authenticated structures, among which the VR-tree is the best choice. The first contribution is the MRtree, a novel index suitable for spatial outsourcing.