{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:14:46Z","timestamp":1784099686174,"version":"3.55.0"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>\n            Sharing trajectories is beneficial for many real-world applications, such as managing disease spread through contact tracing and tailoring public services to a population's travel patterns. However, public concern over privacy and data protection has limited the extent to which this data is shared. Local differential privacy enables data sharing in which users share a perturbed version of their data, but existing mechanisms fail to incorporate user-independent public knowledge (e.g., business locations and opening times, public transport schedules, geo-located tweets). This limitation makes mechanisms too restrictive, gives unrealistic outputs, and ultimately leads to low practical utility. To address these concerns, we propose a local differentially private mechanism that is based on perturbing hierarchically-structured, overlapping\n            <jats:italic>n<\/jats:italic>\n            -grams (i.e., contiguous subsequences of length\n            <jats:italic>n<\/jats:italic>\n            ) of trajectory data. Our mechanism uses a multi-dimensional hierarchy over publicly available external knowledge of real-world places of interest to improve the realism and utility of the perturbed, shared trajectories. Importantly, including real-world public data does not negatively affect privacy or efficiency. Our experiments, using real-world data and a range of queries, each with real-world application analogues, demonstrate the superiority of our approach over a range of alternative methods.\n          <\/jats:p>","DOI":"10.14778\/3476249.3476280","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2283-2295","source":"Crossref","is-referenced-by-count":53,"title":["Real-world trajectory sharing with local differential privacy"],"prefix":"10.14778","volume":"14","author":[{"given":"Teddy","family":"Cunningham","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Graham","family":"Cormode","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hakan","family":"Ferhatosmanoglu","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Divesh","family":"Srivastava","sequence":"additional","affiliation":[{"name":"AT&amp;T Chief Data Office"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Jayadev Acharya Keith Bonawitz Peter Kairouz Daniel Ramage and Ziteng Sun. 2019. Context-Aware Local Differential Privacy. arXiv:1911.00038  Jayadev Acharya Keith Bonawitz Peter Kairouz Daniel Ramage and Ziteng Sun. 2019. Context-Aware Local Differential Privacy. arXiv:1911.00038"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623361"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2018.00026"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516735"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294989"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2505515.2505553"},{"key":"e_1_2_1_7_1","volume-title":"Retrieved","author":"US Census Bureau","year":"2020","unstructured":"US Census Bureau . 2020 . North American Industry Classification System . Retrieved May 12, 2021 from https:\/\/www.census.gov\/naics\/ US Census Bureau. 2020. North American Industry Classification System. Retrieved May 12, 2021 from https:\/\/www.census.gov\/naics\/"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.132"},{"key":"e_1_2_1_9_1","volume-title":"Nicol\u00e1s Emilio Bordenabe, and Catuscia Palamidessi","author":"Chatzikokolakis Konstantinos","year":"2013","unstructured":"Konstantinos Chatzikokolakis , Miguel E. Andr\u00e9s , Nicol\u00e1s Emilio Bordenabe, and Catuscia Palamidessi . 2013 . Broadening the Scope of Differential Privacy Using Metrics. In Privacy Enhancing Technologies . 82--102. Konstantinos Chatzikokolakis, Miguel E. Andr\u00e9s, Nicol\u00e1s Emilio Bordenabe, and Catuscia Palamidessi. 2013. Broadening the Scope of Differential Privacy Using Metrics. In Privacy Enhancing Technologies. 82--102."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2382196.2382263"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498248"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316303"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3469830.3470893"},{"key":"e_1_2_1_15_1","unstructured":"Damien Desfontaines Esfandiar Mohammadi Elisabeth Krahmer and David Basin. 2020. Differential privacy with partial knowledge. (2020). arXiv:1905.00650  Damien Desfontaines Esfandiar Mohammadi Elisabeth Krahmer and David Basin. 2020. Differential privacy with partial knowledge. (2020). arXiv:1905.00650"},{"key":"e_1_2_1_16_1","volume-title":"Retrieved","author":"Developers Foursquare","year":"2020","unstructured":"Foursquare Developers . 2020 . Venue Categories . Retrieved May 24, 2021 from https:\/\/developer.foursquare.com\/docs\/build-with-foursquare\/categories\/ Foursquare Developers. 2020. Venue Categories. Retrieved May 24, 2021 from https:\/\/developer.foursquare.com\/docs\/build-with-foursquare\/categories\/"},{"key":"e_1_2_1_17_1","unstructured":"Apple Differential Privacy Team. 2017. Learning with Privacy at Scale. https:\/\/machinelearning.apple.com\/research\/learning-with-privacy-at-scale  Apple Differential Privacy Team. 2017. Learning with Privacy at Scale. https:\/\/machinelearning.apple.com\/research\/learning-with-privacy-at-scale"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294996.3295115"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806787"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Fatima Zahra Errounda and Yan Liu. 2020. An Analysis of Differential Privacy Research in Location and Trajectory Data. (2020). https:\/\/assets.researchsquare.com\/files\/rs-94765\/v1_stamped.pdf  Fatima Zahra Errounda and Yan Liu. 2020. An Analysis of Differential Privacy Research in Location and Trajectory Data. (2020). https:\/\/assets.researchsquare.com\/files\/rs-94765\/v1_stamped.pdf","DOI":"10.21203\/rs.3.rs-94765\/v1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CNS.2019.8802778"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00050"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2018.2874008"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Mehmet Emre Gursoy Vivekanand Rajasekar and Ling Liu. 2020. Utility-Optimized Synthesis of Differentially Private Location Traces. (2020). arXiv:2009.06505  Mehmet Emre Gursoy Vivekanand Rajasekar and Ling Liu. 2020. Utility-Optimized Synthesis of Differentially Private Location Traces. (2020). arXiv:2009.06505","DOI":"10.1109\/TPS-ISA50397.2020.00015"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809978"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/CNS.2018.8433200"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3423165"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732989"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213571"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808769.2808776"},{"key":"e_1_2_1_35_1","volume-title":"Differentially Private Trajectory Analysis for Points-of-Interest Recommendation. In IEEE International Congress on Big Data. 49--56","author":"Li Chao","year":"2017","unstructured":"Chao Li , Balaji Palanisamy , and James Joshi . 2017 . Differentially Private Trajectory Analysis for Points-of-Interest Recommendation. In IEEE International Congress on Big Data. 49--56 . Chao Li, Balaji Palanisamy, and James Joshi. 2017. Differentially Private Trajectory Analysis for Points-of-Interest Recommendation. In IEEE International Congress on Big Data. 49--56."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508859.2516686"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98161-1_5"},{"key":"e_1_2_1_38_1","first-page":"193","article-title":"Permute-and-Flip: A new mechanism for differentially private selection","volume":"33","author":"McKenna Ryan","year":"2020","unstructured":"Ryan McKenna and Daniel R Sheldon . 2020 . Permute-and-Flip: A new mechanism for differentially private selection . In Advances in Neural Information Processing Systems , Vol. 33. 193 -- 203 . https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/01e00f2f4bfcbb7505cb641066f2859b-Paper.pdf Ryan McKenna and Daniel R Sheldon. 2020. Permute-and-Flip: A new mechanism for differentially private selection. In Advances in Neural Information Processing Systems, Vol. 33. 193--203. https:\/\/proceedings.neurips.cc\/paper\/2020\/file\/01e00f2f4bfcbb7505cb641066f2859b-Paper.pdf","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_40_1","volume-title":"Retrieved","author":"University of British Columbia.","year":"2016","unstructured":"University of British Columbia. 2016 . ubcv-buildings . Retrieved May 12, 2021 from https:\/\/github.com\/UBCGeodata\/ubcv-buildings University of British Columbia. 2016. ubcv-buildings. Retrieved May 12, 2021 from https:\/\/github.com\/UBCGeodata\/ubcv-buildings"},{"key":"e_1_2_1_41_1","volume-title":"Safegraph Places Schema. Retrieved","year":"2020","unstructured":"Safegraph. 2020. Safegraph Places Schema. Retrieved December 7, 2020 from https:\/\/docs.safegraph.com\/v4.0\/docs\/places-schema Safegraph. 2020. Safegraph Places Schema. Retrieved December 7, 2020 from https:\/\/docs.safegraph.com\/v4.0\/docs\/places-schema"},{"key":"e_1_2_1_42_1","volume-title":"TLC Trip Record Data. Retrieved","author":"New York City Taxi and Limousine Commission","year":"2013","unstructured":"New York City Taxi and Limousine Commission . 2013. TLC Trip Record Data. Retrieved March 2, 2013 from https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page New York City Taxi and Limousine Commission. 2013. TLC Trip Record Data. Retrieved March 2, 2013 from https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381105"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/3241189.3241247"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.2014.2327053"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476280","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:02:07Z","timestamp":1672221727000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476280"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":45,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476280"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476280","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}