Publication Type
Conference Proceeding Article
Version
acceptedVersion
Publication Date
4-2020
Abstract
With spatial crowdsourcing applications such as Uber and Waze deeply penetrated into everyday life, there is a growing concern to protect user privacy in spatial crowdsourcing. Particularly, locations of workers and tasks should be properly processed via certain privacy mechanism before reporting to the untrusted spatial crowdsourcing server for task assignment. Privacy mechanisms typically permute the location information, which tends to make task assignment ineffective. Prior studies only provide guarantees on privacy protection without assuring the effectiveness of task assignment. In this paper, we investigate privacy protection for online task assignment with the objective of minimizing the total distance, an important task assignment formulation in spatial crowdsourcing. We design a novel privacy mechanism based on Hierarchically Well-Separated Trees (HSTs). We prove that the mechanism is ε-Geo-Indistinguishable and show that there is a task assignment algorithm with a competitive ratio of O(1ε4logNlog2k), where is the privacy budget, N is the number of predefined points on the HST, and k is the matching size. Extensive experiments on synthetic and real datasets show that online task assignment under our privacy mechanism is notably more effective in terms of total distance than under prior differentially private mechanisms.
Discipline
Computer Engineering
Research Areas
Software and Cyber-Physical Systems
Publication
Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE), Dallas Texas, 2020 April 20-24
First Page
1
Last Page
12
Identifier
10.1109/ICDE48307.2020.00051
Publisher
IEEE
City or Country
Dallas, TX, USA
Citation
TAO, Qian; TONG, Yongxin; ZHOU, Zimu; SHI, Yexuan; CHEN, Lei; and XU, Ke.
Differentially private online task assignment in spatial crowdsourcing: A tree-based approach. (2020). Proceedings of the 36th IEEE International Conference on Data Engineering (ICDE), Dallas Texas, 2020 April 20-24. 1-12.
Available at: https://ink.library.smu.edu.sg/sis_research/5135
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1109/ICDE48307.2020.00051