Publication Type

Conference Proceeding Article

Version

submittedVersion

Publication Date

3-2010

Abstract

Shortest path search in transportation networks is unarguably one of the most important online search services nowadays (e.g., Google Maps, MapQuest, etc), with applications spanning logistics, spatial optimization, or everyday driving decisions. Often times, the owner of the road network data (e.g., a transport authority) provides its database to third-party query services, which are responsible for answering shortest path queries posed by their clients. The issue arising here is that a query service might be returning sub-optimal paths either purposely (in order to serve its own purposes like computational savings or commercial reasons) or because it has been compromised by Internet attackers who falsify the results. Therefore, for the above applications to succeed, it is essential that each reported path is accompanied by a proof, which allows clients to verify the path's correctness. This is the first study on shortest path verification in outsourced network databases. We propose the concept of authenticated hints, which is used to reduce the size of the proofs. We develop several authentication techniques and quantify their tradeoffs with respect to offline construction cost and proof size. Experiments on real road networks demonstrate that our solutions are indeed efficient and lead to compact query proofs.

Keywords

Authentication techniques, Computational savings, Construction costs, Google maps, MapQuest, Network database, Offline, Online search, Optimal paths, Query service, Real road networks, Road network data, Shortest path, Spatial optimization, Transport authorities, Transportation network

Discipline

Databases and Information Systems | Numerical Analysis and Scientific Computing

Publication

ICDE 2010: IEEE 26th International Conference on Data Engineering: Long Beach, California, USA, 1 - 6 March 2010

First Page

237

Last Page

248

ISBN

9781424454457

Identifier

10.1109/ICDE.2010.5447914

Publisher

IEEE Computer Society

City or Country

Los Alamitos, CA

Additional URL

http://doi.ieeecomputersociety.org/10.1109/ICDE.2010.5447914

Download

Share

COinS