{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:01:41Z","timestamp":1774983701024,"version":"3.50.1"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"the National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62402195"],"award-info":[{"award-number":["62402195"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>Range counting is a fundamental operation in spatial data applications. There is a growing demand to facilitate this operation over a data federation, where spatial data are separately held by multiple data providers (a.k.a., data silos). Most existing data federation schemes employ Secure Multiparty Computation (SMC) to protect privacy, but this approach is computationally expensive and leads to high latency. Consequently, private data federations are often impractical for typical database workloads.This challenge highlights the need for a private data federation scheme capable of providing fast and accurate query responses while maintaining strong privacy.<\/jats:p>\n                  <jats:p>To address this issue, we propose U-DPAP, a utility-aware efficient privacy-preserving method. It is the first scheme to exclusively use differential privacy for privacy protection in spatial data federation, without employing SMC. Moreover, it combines approximate query processing to further enhance efficiency. Our experimental results indicate that a straightforward combination of the two techniques results in unacceptable impacts on data utility. Thus, we design two novel algorithms: one to make differential privacy practical by optimizing the privacy-utility trade-off, and another to address the efficiency-utility trade-off in approximate query processing. The grouping-based perturbation algorithm reduces noise by grouping similar data and applying noise to the groups. The representative data silos selection algorithm minimizes approximate error by selecting representative silos using the similarity between data silos. We rigorously prove the privacy guarantees of U-DPAP. Moreover, experimental results demonstrate that U-DPAP enhances data utility by an order of magnitude while maintaining high communication efficiency.<\/jats:p>","DOI":"10.1145\/3714333","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-25","source":"Crossref","is-referenced-by-count":0,"title":["U-DPAP: Utility-aware Efficient Range Counting on Privacy-preserving Spatial Data Federation"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-9929-5379","authenticated-orcid":false,"given":"Yahong","family":"Chen","sequence":"first","affiliation":[{"name":"Central China Normal University, Wuhan, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2763-2695","authenticated-orcid":false,"given":"Xiaoyi","family":"Pang","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1839-1607","authenticated-orcid":false,"given":"Xiaoguang","family":"Li","sequence":"additional","affiliation":[{"name":"Xidian University, Xian, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5542-165X","authenticated-orcid":false,"given":"Hanyi","family":"Wang","sequence":"additional","affiliation":[{"name":"China Mobile (Suzhou) Software Technology Co., Ltd., Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2898-7495","authenticated-orcid":false,"given":"Ben","family":"Niu","sequence":"additional","affiliation":[{"name":"Institute of Information Engineering, CAS, Beijing, China and Key Laboratory of Cyberspace Security Defense, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7771-7339","authenticated-orcid":false,"given":"Shengnan","family":"Hu","sequence":"additional","affiliation":[{"name":"Central China Normal University, Wuhan, China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2021. 9 Bike. http:\/\/www.9bikelm.com"},{"key":"e_1_2_1_2_1","unstructured":"Gergely Acs and Claude Castelluccia. 2014. A case study: Privacy preserving release of spatio-temporal density in paris. In ACM SIGKDD."},{"key":"e_1_2_1_3_1","unstructured":"Ablimit Aji Fusheng Wang Hoang Vo Rubao Lee Qiaoling Liu Xiaodong Zhang and Joel Saltz. 2013. Hadoop-GIS: A high performance spatial data warehousing system over MapReduce. In Morgan Kaufmann\/ACM VLDB."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-020-10486-4"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Johes Bater Xi He William Ehrich Ashwin Machanavajjhala and Jennie Rogers. 2018. Shrinkwrap: efficient sql query processing in differentially private data federations. In Morgan Kaufmann\/ACM VLDB.","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Johes Bater Yongjoo Park Xi He Xiao Wang and Jennie Rogers. 2020. Saqe: practical privacy-preserving approximate query processing for data federations. In Morgan Kaufmann\/ACM VLDB.","DOI":"10.14778\/3407790.3407854"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/767141.767147"},{"key":"e_1_2_1_9_1","volume-title":"Shiva Prasad Kasiviswanathan, and Hongxia Jin","author":"Chen Rui","year":"2016","unstructured":"Rui Chen, Haoran Li, A Kai Qin, Shiva Prasad Kasiviswanathan, and Hongxia Jin. 2016. Private spatial data aggregation in the local setting. In IEEE ICDE."},{"key":"e_1_2_1_10_1","volume-title":"Sketch techniques for approximate query processing. Foundations and Trends in Databases","author":"Cormode Graham","year":"2011","unstructured":"Graham Cormode. 2011. Sketch techniques for approximate query processing. Foundations and Trends in Databases. NOW publishers 15 (2011)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.16"},{"key":"e_1_2_1_12_1","volume-title":"Differential privacy","author":"Dwork Cynthia","unstructured":"Cynthia Dwork. 2006. Differential privacy. In Springer ICALP."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_2_1_14_1","volume-title":"Spatialhadoop: A mapreduce framework for spatial data","author":"Eldawy Ahmed","year":"2015","unstructured":"Ahmed Eldawy and Mohamed F Mokbel. 2015. Spatialhadoop: A mapreduce framework for spatial data. In IEEE ICDE."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01228709"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30637-2_21"},{"key":"e_1_2_1_17_1","first-page":"3196","article-title":"Distributed multimodal path queries","volume":"34","author":"Li Yawen","year":"2020","unstructured":"Yawen Li, Ye Yuan, YishuWang, Xiang Lian, Yuliang Ma, and GuorenWang. 2020. Distributed multimodal path queries. IEEE Transactions on Knowledge and Data Engineering 34, 7 (2020), 3196--3210.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Frank D McSherry. 2009. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In ACM SIGMOD.","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Prashanth Mohan Abhradeep Thakurta Elaine Shi Dawn Song and David Culler. 2012. GUPT: privacy preserving data analysis made easy. In ACM SIGMOD.","DOI":"10.1145\/2213836.2213876"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544872"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/96602.96604"},{"key":"e_1_2_1_22_1","first-page":"418","article-title":"Efficient approximate range aggregation over large-scale spatial data federation","volume":"35","author":"Shi Yexuan","year":"2021","unstructured":"Yexuan Shi, Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Bolin Ding, and Lei Chen. 2021. Efficient approximate range aggregation over large-scale spatial data federation. IEEE Transactions on Knowledge and Data Engineering 35, 1 (2021), 418--430.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_23_1","unstructured":"Hien To Gabriel Ghinita and Cyrus Shahabi. 2014. A framework for protecting worker location privacy in spatial crowdsourcing. In Morgan Kaufmann\/ACM VLDB."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3514061.3514064"},{"key":"e_1_2_1_25_1","unstructured":"Nikolaj Volgushev Malte Schwarzkopf Ben Getchell Mayank Varia Andrei Lapets and Azer Bestavros. 2019. Conclave: secure multi-party computation on big data. In ACM EuroSys."},{"key":"e_1_2_1_26_1","unstructured":"Xuan-Son Vu Addi Ait-Mlouk Erik Elmroth and Lili Jiang. 2019. Graph-based interactive data federation system for heterogeneous data retrieval and analytics. In ACM WWW."},{"key":"e_1_2_1_27_1","volume-title":"Simba: Efficient in-memory spatial analytics","author":"Xie Dong","year":"2016","unstructured":"Dong Xie, Feifei Li, Bin Yao, Gefei Li, Liang Zhou, and Minyi Guo. 2016. Simba: Efficient in-memory spatial analytics. In IEEE ICDE."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Ye Yuan Delong Ma Zhenyu Wen Zhiwei Zhang and Guoren Wang. 2021. Subgraph matching over graph federation. In Morgan Kaufmann\/ACM VLDB.","DOI":"10.14778\/3494124.3494129"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30637-2_23"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-020-01450-7"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3222415"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3714333","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3714333","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:19:59Z","timestamp":1774981199000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3714333"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3714333"],"URL":"https:\/\/doi.org\/10.1145\/3714333","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}