Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/18220
DC FieldValueLanguage
dc.contributorDepartment of Computing-
dc.creatorYiu, ML-
dc.creatorLin, Y-
dc.creatorMouratidis, K-
dc.date.accessioned2015-09-30T09:43:42Z-
dc.date.available2015-09-30T09:43:42Z-
dc.identifier.isbn978-1-4244-5445-7-
dc.identifier.isbn978-1-4244-5444-0 (E-ISBN)-
dc.identifier.urihttp://hdl.handle.net/10397/18220-
dc.language.isoenen_US
dc.publisherIEEEen_US
dc.subjectAuthorisationen_US
dc.subjectGraph theoryen_US
dc.subjectInformation retrieval systemsen_US
dc.subjectInformation servicesen_US
dc.subjectSearch problemsen_US
dc.titleEfficient verification of shortest path search via authenticated hintsen_US
dc.typeConference Paperen_US
dc.identifier.spage237-
dc.identifier.epage248-
dc.identifier.doi10.1109/ICDE.2010.5447914-
dcterms.abstractShortest 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.-
dcterms.bibliographicCitation2010 IEEE 26th International Conference on Data Engineering (ICDE), 1-6 March 2010, Long Beach, CA, p. 237-248-
dcterms.issued2010-
dc.relation.ispartofbook2010 IEEE 26th International Conference on Data Engineering (ICDE), 1-6 March 2010, Long Beach, CA-
dc.relation.conferenceIEEE International Conference on Data Engineering [ICDE]-
dc.identifier.rosgroupidr46924-
dc.description.ros2009-2010 > Academic research: refereed > Refereed conference paper-
Appears in Collections:Conference Paper
Access
View full-text via PolyU eLinks SFX Query
Show simple item record

SCOPUSTM   
Citations

44
Last Week
0
Last month
Citations as of Aug 7, 2020

WEB OF SCIENCETM
Citations

31
Last Week
0
Last month
0
Citations as of Oct 29, 2020

Page view(s)

133
Last Week
0
Last month
Citations as of Oct 25, 2020

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.