.png){kind=icon}
Return
Location Problems with Privacy
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-10759-6_2.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
We examine well known facility location problems under the privacy challenges posed by big data environments. For a given set of n points U is an element of R-d, previous works have introduced the Topology Descriptor Grid (TDG) [13, 14], a privacy-preserving framework under which some approximate solutions are possible for a variety of clustering problems. In this paper, we introduce the Equidistant Location Estimation using Concentric Circles (LECC) framework in R-2, which obfuscates exact point locations while preserving their relative distances to a predetermined point. We show, under this new framework, how to obtain 2 + O(1/n)-approximate solutions for the 1-center, 1-median, 1-mean, and k-centrum problems, and O(k), O(k), O(k(2)) approximations for the k-center, k-median and k-means problems, respectively. For the TDG framework we provide a (root d, k(d-1)),(d, k(d-1)), and(d(2), k(d-1)) approximations for the k-center, k-median, and k-means problems, respectively.
Keywords:
Facility location
Privacy
Approximation algorithms
Journal
C
IF:
0
Papers:
25
Citations:
0
Organization
Cited Papers
ShareSaveDifferential privacy for location pattern mining.png)
Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBS
Proceedings of the 4th ACM SIGSPATIAL International Workshop on Security and Privacy in GIS and LBSIF0
PREAI
ShareSaveShareSave
ShareSaveGeo-indistinguishabilityProceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13
OAAI
Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13IF0
OAAIShareSaveDeterministic wavelet thresholding for maximum-error metricsProceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsIF0
PREAI
ShareSave
View more