Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/3235

Spatial outsourcing for location-based services

Authors Yang, Y.
Papadopoulos, S.
Papadias, D.
Kollios, G.
Issue Date 2008
Source Proceedings - International Conference on Data Engineering, 2008, p. 1082-1091
Summary The embedding of positioning capabilities in mobile devices and the emergence of location-based applications have created novel opportunities lor 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 multidimensional authenticated structures, among which the VR-tree is the best choice. Our first contribution is the MR-tree, a novel index suitable for spatial outsourcing. We show, analytically and experimentally, that the MR-tree outperforms the VR-tree, usually by orders of magnitude, on all performance metrics, including construction cost, index size, query and verification overhead. Motivated by the fact that successive queries by the same mobile client exhibit locality, we also propose a synchronized caching technique that utilizes the results of previous queries to reduce the size of the additional information sent to the client for verification purposes. © 2008 IEEE.
Subjects
ISSN 1084-4627
ISBN 978-1-4244-1836-7
Rights © 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.
Language English
Format Conference paper
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science
Find@HKUST
Files in this item:
File Description Size Format
04497517.pdf 4.84 MB Adobe PDF