{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T17:54:39Z","timestamp":1773510879363,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,4]]},"abstract":"<jats:p>Shortest path computation is one of the most common queries in location-based services (LBSs). Although particularly useful, such queries raise serious privacy concerns. Exposing to a (potentially untrusted) LBS the client's position and her destination may reveal personal information, such as social habits, health condition, shopping preferences, lifestyle choices, etc. The only existing method for privacy-preserving shortest path computation follows the obfuscation paradigm; it prevents the LBS from inferring the source and destination of the query with a probability higher than a threshold. This implies, however, that the LBS still deduces some information (albeit not exact) about the client's location and her destination. In this paper we aim at strong privacy, where the adversary learns nothing about the shortest path query. We achieve this via established private information retrieval techniques, which we treat as black-box building blocks. Experiments on real, large-scale road networks assess the practicality of our schemes.<\/jats:p>","DOI":"10.14778\/2212351.2212352","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"692-703","source":"Crossref","is-referenced-by-count":56,"title":["Shortest path computation with no information leakage"],"prefix":"10.14778","volume":"5","author":[{"given":"Kyriakos","family":"Mouratidis","sequence":"first","affiliation":[{"name":"Singapore Management University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Man Lung","family":"Yiu","sequence":"additional","affiliation":[{"name":"Hong Kong Polytechnic University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPRV.2003.1186725"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11593447_13"},{"key":"e_1_2_1_3_1","unstructured":"J. Cheng. How Apple tracks your location without your consent and why it matters. http:\/\/arstechnica.com\/apple\/news\/2011\/04\/how-apple-tracks-your-location-without-your-consent-and-why-it-matters.ars April 2011.  J. Cheng. How Apple tracks your location without your consent and why it matters. http:\/\/arstechnica.com\/apple\/news\/2011\/04\/how-apple-tracks-your-location-without-your-consent-and-why-it-matters.ars April 2011."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796270"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183471.1183500"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2007.52"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/11428572_10"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989367"},{"key":"e_1_2_1_10_1","first-page":"72","article-title":"A survey on private information retrieval (column: Computational complexity)","volume":"82","author":"Gasarch W. I.","year":"2004","unstructured":"W. I. Gasarch . A survey on private information retrieval (column: Computational complexity) . Bulletin of the EATCS , 82 : 72 -- 107 , 2004 . W. I. Gasarch. A survey on private information retrieval (column: Computational complexity). Bulletin of the EATCS, 82:72--107, 2004.","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376631"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242623"},{"key":"e_1_2_1_13_1","first-page":"156","volume-title":"SODA","author":"Goldberg A. V.","year":"2005","unstructured":"A. V. Goldberg and C. Harrelson . Computing the shortest path: A* search meets graph theory . In SODA , pages 156 -- 165 , 2005 . A. V. Goldberg and C. Harrelson. Computing the shortest path: A* search meets graph theory. In SODA, pages 156--165, 2005."},{"issue":"2","key":"e_1_2_1_14_1","first-page":"100","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart P.","year":"1968","unstructured":"P. Hart , N. Nilsson , and B. Raphael . A formal basis for the heuristic determination of minimum cost paths . IEEE TSSC , 4 ( 2 ): 100 -- 107 , 1968 . P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE TSSC, 4(2):100--107, 1968.","journal-title":"IEEE TSSC"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1033772"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190662"},{"issue":"1","key":"e_1_2_1_17_1","first-page":"747","article-title":"Shortest path computation on air indexes","volume":"3","author":"Kellaris G.","year":"2010","unstructured":"G. Kellaris and K. Mouratidis . Shortest path computation on air indexes . PVLDB , 3 ( 1 ): 747 -- 757 , 2010 . G. Kellaris and K. Mouratidis. Shortest path computation on air indexes. PVLDB, 3(1):747--757, 2010.","journal-title":"PVLDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1784462.1784476"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0286-z"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/PERSER.2005.1506394"},{"key":"e_1_2_1_21_1","first-page":"41","volume-title":"9th DIMACS Implementation Challenge - Shortest Paths","author":"K\u00f6hler E.","year":"2006","unstructured":"E. K\u00f6hler , R. H. M\u00f6hring , and H. Schilling . Fast point-to-point shortest path computations with arc-flags . In 9th DIMACS Implementation Challenge - Shortest Paths , pages 41 -- 72 , 2006 . E. K\u00f6hler, R. H. M\u00f6hring, and H. Schilling. Fast point-to-point shortest path computations with arc-flags. In 9th DIMACS Implementation Challenge - Shortest Paths, pages 41--72, 2006."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1645953.1646041"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142488"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1187436.1216585"},{"key":"e_1_2_1_25_1","first-page":"763","volume-title":"VLDB","author":"Mokbel M. F.","year":"2006","unstructured":"M. F. Mokbel , C.-Y. Chow , and W. G. Aref . The new Casper: Query processing for location services without compromising privacy . In VLDB , pages 763 -- 774 , 2006 . M. F. Mokbel, C.-Y. Chow, and W. G. Aref. The new Casper: Query processing for location services without compromising privacy. In VLDB, pages 763--774, 2006."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2009.48"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066204"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920920"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2011.17"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01645-5_3"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376623"},{"key":"e_1_2_1_32_1","volume-title":"NDSS","author":"Sion R.","year":"2007","unstructured":"R. Sion and B. Carbunar . On the practicality of private information retrieval . In NDSS , 2007 . R. Sion and B. Carbunar. On the practicality of private information retrieval. In NDSS, 2007."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218488502001648"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687745"},{"key":"e_1_2_1_35_1","unstructured":"C. Williams. Apple under pressure over iphone location tracking. http:\/\/www.telegraph.co.uk\/technology\/apple\/8466357\/Apple-under-pressure-over-iPhone-location-tracking.html April 2011.  C. Williams. Apple under pressure over iphone location tracking. http:\/\/www.telegraph.co.uk\/technology\/apple\/8466357\/Apple-under-pressure-over-iPhone-location-tracking.html April 2011."},{"key":"e_1_2_1_36_1","volume-title":"NDSS","author":"Williams P.","year":"2008","unstructured":"P. Williams and R. Sion . Usable PIR . In NDSS , 2008 . P. Williams and R. Sion. Usable PIR. In NDSS, 2008."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559862"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-009-0169-7"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497445"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447914"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2212351.2212352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:34:55Z","timestamp":1672220095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2212351.2212352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,4]]},"references-count":40,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2012,4]]}},"alternative-id":["10.14778\/2212351.2212352"],"URL":"https:\/\/doi.org\/10.14778\/2212351.2212352","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,4]]}}}