{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:39:08Z","timestamp":1740123548720,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"16","license":[{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T00:00:00Z","timestamp":1654473600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"crossref","award":["NRF-2022R1H1A2005355"],"award-info":[{"award-number":["NRF-2022R1H1A2005355"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2022,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>During the past decades, maximum influential location selection (Max-inf) problems have been of intense interest to the spatial database community. The Max-inf problem searches for a location that attracts as many clients as possible, so it is essential to collect the location information of each client for such a query. However, the client location is considered sensitive information, and location privacy has become an emerging issue. To resolve the privacy issue, we present a novel Max-inf problem in a differentially private manner, which is called DP-Max-inf in a road network. Differential privacy is a de-facto standard privacy protection technique that injects controlled noise into statistical query results. In addition, we present the influence region overlapping problem while applying differential privacy to the Max-inf problem using the conventional approach. To remedy this problem, we propose a network Voronoi region-based technique to guarantee query accuracy and a network Voronoi envelope-based pruning heuristic to improve query performance.<\/jats:p>","DOI":"10.1007\/s11227-022-04601-5","type":"journal-article","created":{"date-parts":[[2022,6,6]],"date-time":"2022-06-06T07:03:53Z","timestamp":1654499033000},"page":"18336-18360","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Nearly most influential location selection with differentially private user locations in a road network"],"prefix":"10.1007","volume":"78","author":[{"given":"Sehwa","family":"Park","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4049-7950","authenticated-orcid":false,"given":"Seog","family":"Park","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,6]]},"reference":[{"key":"4601_CR1","doi-asserted-by":"crossref","unstructured":"Xiao X, Yao B, Li F (2011) Optimal location queries in road network databases. In: 2011 IEEE 27th International Conference on Data Engineering, pp 804\u2013815","DOI":"10.1109\/ICDE.2011.5767845"},{"issue":"5","key":"4601_CR2","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/s00778-013-0347-5","volume":"23","author":"B Yao","year":"2014","unstructured":"Yao B, Xiao X, Li F, Wu Y (2014) Dynamic monitoring of optimal locations in road network databases. VLDB J 23(5):697\u2013720","journal-title":"VLDB J"},{"key":"4601_CR3","doi-asserted-by":"crossref","unstructured":"Chen Z, Liu Y, Fu AW, Wong RC, Dai G (2019) Kolq in a road network. In: 2019 20th IEEE International Conference on Mobile Data Management (MDM), pp 81\u201390","DOI":"10.1109\/MDM.2019.00-71"},{"key":"4601_CR4","doi-asserted-by":"publisher","unstructured":"Li N, Lyu M, Su D, Yang W(2016) https:\/\/doi.org\/10.2200\/S00735ED1V01Y201609SPT018","DOI":"10.2200\/S00735ED1V01Y201609SPT018"},{"issue":"3\u20134","key":"4601_CR5","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1561\/0400000042","volume":"9","author":"C Dwork","year":"2014","unstructured":"Dwork C, Roth A (2014) The algorithmic foundations of differential privacy. Found Trends Theor Comput Sci 9(3\u20134):211\u2013407. https:\/\/doi.org\/10.1561\/0400000042","journal-title":"Found Trends Theor Comput Sci"},{"key":"4601_CR6","doi-asserted-by":"publisher","first-page":"83728","DOI":"10.1109\/ACCESS.2020.2990706","volume":"8","author":"S Park","year":"2020","unstructured":"Park S, Lee J, Park S (2020) Maximum influential location selection with differentially private user locations. IEEE Access 8:83728\u201383744. https:\/\/doi.org\/10.1109\/ACCESS.2020.2990706","journal-title":"IEEE Access"},{"issue":"9","key":"4601_CR7","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1080\/13658810701587891","volume":"22","author":"A Okabe","year":"2008","unstructured":"Okabe A, Satoh T, Furuta T, Suzuki A, Okano K (2008) Generalized network Voronoi diagrams: Concepts, computational methods, and applications. Int J Geogr Inf Sci 22(9):965\u2013994. https:\/\/doi.org\/10.1080\/13658810701587891","journal-title":"Int J Geogr Inf Sci"},{"key":"4601_CR8","doi-asserted-by":"publisher","unstructured":"McSherry FD (2009) Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201909, Association for Computing Machinery, New York, NY, USA, pp 19-30. https:\/\/doi.org\/10.1145\/1559845.1559850","DOI":"10.1145\/1559845.1559850"},{"issue":"2","key":"4601_CR9","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/335191.335415","volume":"29","author":"F Korn","year":"2000","unstructured":"Korn F, Muthukrishnan S (2000) Influence sets based on reverse nearest neighbor queries. SIGMOD Rec 29(2):201\u2013212. https:\/\/doi.org\/10.1145\/335191.335415","journal-title":"SIGMOD Rec"},{"issue":"4","key":"4601_CR10","doi-asserted-by":"publisher","first-page":"540","DOI":"10.1109\/TKDE.2006.1599391","volume":"18","author":"ML Yiu","year":"2006","unstructured":"Yiu ML, Papadias D, Mamoulis N, Tao Y (2006) Reverse nearest neighbors in large graphs. IEEE Trans Knowl Data Eng 18(4):540\u2013553","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"4601_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269\u2013271. https:\/\/doi.org\/10.1007\/BF01386390","journal-title":"Numer Math"},{"issue":"5","key":"4601_CR12","doi-asserted-by":"publisher","first-page":"1205","DOI":"10.1109\/TKDE.2014.2365820","volume":"27","author":"Y Gao","year":"2015","unstructured":"Gao Y, Qin X, Zheng B, Chen G (2015) Efficient reverse top-k Boolean spatial keyword queries on road networks. IEEE Trans Knowl Data Eng 27(5):1205\u20131218","journal-title":"IEEE Trans Knowl Data Eng"},{"issue":"1","key":"4601_CR13","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1109\/69.567054","volume":"9","author":"S Shekhar","year":"1997","unstructured":"Shekhar S, Liu D-R (1997) Ccam: a connectivity-clustered access method for networks and network computations. IEEE Trans Knowl Data Eng 9(1):102\u2013119. https:\/\/doi.org\/10.1109\/69.567054","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"4601_CR14","doi-asserted-by":"publisher","unstructured":"Zhao J, Gao Y, Chen G, Jensen CS, Chen R, Cai D (2017) Reverse top-k geo-social keyword queries in road networks. In: 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp 387\u2013398. https:\/\/doi.org\/10.1109\/ICDE.2017.97","DOI":"10.1109\/ICDE.2017.97"},{"key":"4601_CR15","volume-title":"Reverse facility location problems","author":"S Cabello","year":"2006","unstructured":"Cabello S, Diaz-Banez JM, Langerman S, Seara C, Ventura I (2006) Reverse facility location problems. Department of Mathematics, University of Ljubljana, Ljubljana"},{"issue":"1","key":"4601_CR16","doi-asserted-by":"publisher","first-page":"1126","DOI":"10.14778\/1687627.1687754","volume":"2","author":"RC-W Wong","year":"2009","unstructured":"Wong RC-W, \u00d6zsu MT, Yu PS, Fu AW-C, Liu L (2009) Efficient method for maximizing bichromatic reverse nearest neighbor. Proc VLDB Endow 2(1):1126\u20131137. https:\/\/doi.org\/10.14778\/1687627.1687754","journal-title":"Proc VLDB Endow"},{"key":"4601_CR17","doi-asserted-by":"publisher","unstructured":"Yan D, Wong RC-W, Ng W (2011) Efficient methods for finding influential locations with adaptive grids. In: Proceedings of the 20th ACM International Conference on Information and Knowledge Management, CIKM \u201911, Association for Computing Machinery, New York, NY, USA, pp 1475\u20131484. https:\/\/doi.org\/10.1145\/2063576.2063788","DOI":"10.1145\/2063576.2063788"},{"key":"4601_CR18","unstructured":"Zhang D, Du Y, Xia T, Tao Y (2006) Progressive computation of the min-dist optimal-location query. In: Proceedings of the 32nd International Conference on Very Large Data Bases, VLDB \u201906, VLDB Endowment, pp 643\u2013654"},{"key":"4601_CR19","doi-asserted-by":"crossref","unstructured":"Qi J, Zhang R, Kulik L, Lin D, Xue Y (2012) The min-dist location selection query. In: 2012 IEEE 28th International Conference on Data Engineering, pp 366\u2013377","DOI":"10.1109\/ICDE.2012.45"},{"key":"4601_CR20","doi-asserted-by":"publisher","unstructured":"Chen Z, Liu Y, Wong RC-W, Xiong J, Mai G, Long C (2014) Efficient algorithms for optimal location queries in road networks. In: Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data, SIGMOD \u201914, Association for Computing Machinery, New York, NY, USA, pp 123\u2013134. https:\/\/doi.org\/10.1145\/2588555.2612172","DOI":"10.1145\/2588555.2612172"},{"key":"4601_CR21","doi-asserted-by":"publisher","unstructured":"Liu R, Fu AW-C, Chen Z, Huang S, Liu Y (2016) Finding multiple new optimal locations in a road network. In: Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPACIAL \u201916, Association for Computing Machinery, New York, NY, USA. https:\/\/doi.org\/10.1145\/2996913.2996927","DOI":"10.1145\/2996913.2996927"},{"key":"4601_CR22","doi-asserted-by":"crossref","unstructured":"Cormode G, Procopiuc C, Srivastava D, Shen E, Yu T (2012) Differentially private spatial decompositions. In: 2012 IEEE 28th International Conference on Data Engineering, pp 20\u201331","DOI":"10.1109\/ICDE.2012.16"},{"key":"4601_CR23","doi-asserted-by":"crossref","unstructured":"Qardaji W, Yang W, Li N (2013) Differentially private grids for geospatial data. In: 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp 757\u2013768","DOI":"10.1109\/ICDE.2013.6544872"},{"issue":"5","key":"4601_CR24","doi-asserted-by":"publisher","first-page":"341","DOI":"10.14778\/2732269.2732271","volume":"7","author":"C Li","year":"2014","unstructured":"Li C, Hay M, Miklau G, Wang Y (2014) A data- and workload-aware algorithm for range queries under differential privacy. Proc VLDB Endow 7(5):341\u2013352. https:\/\/doi.org\/10.14778\/2732269.2732271","journal-title":"Proc VLDB Endow"},{"key":"4601_CR25","doi-asserted-by":"publisher","unstructured":"Zhang J, Xiao X, Xie X (2016) Privtree: a differentially private algorithm for hierarchical decompositions. In: Proceedings of the 2016 International Conference on Management of Data, SIGMOD \u201916, Association for Computing Machinery, New York, NY, USA, pp 155\u2013170. https:\/\/doi.org\/10.1145\/2882903.2882928","DOI":"10.1145\/2882903.2882928"},{"key":"4601_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1109\/TSC.2019.2920643","volume":"2","author":"J Wei","year":"2019","unstructured":"Wei J, Lin Y, Yao X, Zhang J (2019) Differential privacy-based location protection in spatial crowdsourcing. IEEE Trans Serv Comput 2:1. https:\/\/doi.org\/10.1109\/TSC.2019.2920643","journal-title":"IEEE Trans Serv Comput"},{"issue":"2","key":"4601_CR27","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1109\/TDSC.2017.2693986","volume":"16","author":"E Yilmaz","year":"2019","unstructured":"Yilmaz E, Ferhatosmanoglu H, Ayday E, Aksoy RC (2019) Privacy-preserving aggregate queries for optimal location selection. IEEE Trans Depend Secure Comput 16(2):329\u2013343. https:\/\/doi.org\/10.1109\/TDSC.2017.2693986","journal-title":"IEEE Trans Depend Secure Comput"},{"key":"4601_CR28","doi-asserted-by":"publisher","first-page":"95843","DOI":"10.1109\/ACCESS.2020.2995504","volume":"8","author":"X Yang","year":"2020","unstructured":"Yang X, Gao L, Zheng J, Wei W (2020) Location privacy preservation mechanism for location-based service with incomplete location data. IEEE Access 8:95843\u201395854. https:\/\/doi.org\/10.1109\/ACCESS.2020.2995504","journal-title":"IEEE Access"},{"key":"4601_CR29","doi-asserted-by":"publisher","unstructured":"Gu X, Li M, Cao Y, Xiong L (2019) Supporting both range queries and frequency estimation with local differential privacy. In: IEEE Conference on Communications and Network Security (CNS), pp 124\u2013132. https:\/\/doi.org\/10.1109\/CNS.2019.8802778","DOI":"10.1109\/CNS.2019.8802778"},{"key":"4601_CR30","doi-asserted-by":"publisher","unstructured":"Li F, Cheng D, Hadjieleftheriou M, Kollios G, Teng S-H (2005) On trip planning queries in spatial databases. In: Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases, SSTD\u201905. Springer, Berlin, pp 273\u2013290. https:\/\/doi.org\/10.1007\/11535331_16","DOI":"10.1007\/11535331_16"},{"key":"4601_CR31","unstructured":"Real datasets for spatial databases: road networks and points of interest. https:\/\/www.cs.utah.edu\/~lifeifei\/SpatialDataset.htm"},{"issue":"6","key":"4601_CR32","doi-asserted-by":"publisher","first-page":"2407","DOI":"10.1007\/s11280-019-00682-0","volume":"22","author":"Y Li","year":"2019","unstructured":"Li Y, Cao X, Yuan Y, Wang G (2019) Privsem: protecting location privacy using semantic and differential privacy. World Wide Web 22(6):2407\u20132436","journal-title":"World Wide Web"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04601-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-022-04601-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-022-04601-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,17]],"date-time":"2022-11-17T15:19:37Z","timestamp":1668698377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-022-04601-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,6]]},"references-count":32,"journal-issue":{"issue":"16","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["4601"],"URL":"https:\/\/doi.org\/10.1007\/s11227-022-04601-5","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"type":"print","value":"0920-8542"},{"type":"electronic","value":"1573-0484"}],"subject":[],"published":{"date-parts":[[2022,6,6]]},"assertion":[{"value":"6 May 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 June 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}