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

Additional URL

https://doi.org/10.1109/ICDE48307.2020.00051

Share

COinS