The DOI matches its Crossref record; 30 of the 30 references it cites were found in a registry or an index.
Differentially Private Spatial Decompositions
Open accessAbstract
Differential privacy has recently emerged as the de facto standard for private data release. This makes it possible to provide strong theoretical guarantees on the privacy and utility of released data. While it is well-understood how to release data based on counts and simple functions under this guarantee, it remains to provide general purpose techniques to release data that is useful for a variety of queries. In this paper, we focus on spatial data such as locations and more generally any multi-dimensional data that can be indexed by a tree structure. Directly applying existing differential privacy methods to this type of data simply generates noise. We propose instead the class of "private spatial decompositions'': these adapt standard spatial indexing methods such as quad trees and kd-trees to provide a private description of the data distribution. Equipping such structures with differential privacy requires several steps to ensure that they provide meaningful privacy guarantees. Various basic steps, such as choosing splitting points and describing the distribution of points within a region, must be done privately, and the guarantees of the different building blocks composed to provide an overall guarantee. Consequently, we expose the design space for private spatial decompositions, and analyze some key examples. A major contribution of our work is to provide new techniques for parameter setting and post-processing the output to improve the accuracy of query answers. Our experimental study demonstrates that it is possible to build such decompositions efficiently, and use them to answer a variety of queries privately with high accuracy.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Linear Statistical Inference and its Applications: Second Editon
Rao, C. R. (1973) · Wiley Series in Probability and Statistics · doi:10.1002/9780470316436 · Cited by 10,489
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Computational Geometry: Algorithms and Applications
de Berg, M., Cheong, O., van Kreveld, M. J., & Overmars, M. H. (1997) · CERN Document Server (European Organization for Nuclear Research) · Cited by 4,450
L -diversity: Privacy beyond k -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.1 · Cited by 2,362
Computational Geometry: Algorithms and Applications
de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008) · Springer eBooks · doi:10.1007/978-3-540-77974-2 · Cited by 1,999
Foundations of Multidimensional and Metric Data Structures
Samet, H., & Gray, J. (2006) · Cited by 1,373
Mechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.66 · Cited by 1,371
Samarati, P., & Sweeney, L. (2018) · doi:10.1184/r1/6625469 · Cited by 1,326
Towards Sharp Inapproximability For Any 2-CSP
Austrin, P. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.41 · Cited by 1,294
Privacy integrated queries: an extensible platform for privacy-preserving data analysis
McSherry, F. D. (2009) · Proceedings of the 2009 ACM SIGMOD International Conference on Management of data · doi:10.1145/1559845.1559850 · Cited by 1,124
Smooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974
A firm foundation for private data analysis
Dwork, C. (2011) · Communications of the ACM · doi:10.1145/1866739.1866758 · Cited by 841
Linear statistical inference and its applications
Chistyakov, V. P. (1966) · USSR Computational Mathematics and Mathematical Physics · doi:10.1016/0041-5553(66)90024-3 · Cited by 705
Differentially private recommender systems: Building privacy into the Netflix Prize contenders
McSherry, F., & Mironov, I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557090 · Cited by 664
Differentially private aggregation of distributed time-series with transformation and encryption
Rastogi, V., & Nath, S. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807247 · Cited by 534
Boosting the accuracy of differentially private histograms through consistency
Hay, M., Rastogi, V., Miklau, G., & Suciu, D. (2010) · Proceedings of the VLDB Endowment · doi:10.14778/1920841.1920970 · Cited by 528
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., & Talwar, K. (2007) · Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1265530.1265569 · Cited by 468
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2017) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v7i3.405 · Cited by 390
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Optimizing linear counting queries under differential privacy
Li, C., Hay, M., Rastogi, V., Miklau, G., & McGregor, A. (2010) · Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1807085.1807104 · Cited by 319
Universally utility-maximizing privacy mechanisms
Ghosh, A., Roughgarden, T., & Sundararajan, M. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536464 · Cited by 246
Differential privacy via wavelet transforms
Xiao, X., Wang, G., & Gehrke, J. (2010) · 2010 IEEE 26th International Conference on Data Engineering (ICDE 2010) · doi:10.1109/icde.2010.5447831 · Cited by 178
Differentially Private Data Release through Multidimensional Partitioning
Xiao, Y., Xiong, L., & Yuan, C. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-15546-8_11 · Cited by 169
Private record matching using differential privacy
Inan, A., Kantarcioglu, M., Ghinita, G., & Bertino, E. (2010) · Proceedings of the 13th International Conference on Extending Database Technology · doi:10.1145/1739041.1739059 · Cited by 162
Privacy-Preserving Data Publishing
Chen, B.-C., Kifer, D., LeFevre, K., & Machanavajjhala, A. (2009) · Foundations and Trends in Databases · doi:10.1561/1900000008 · Cited by 147
Privacy-Preserving Data Publishing
Chen, B.-C., Kifer, D., LeFevre, K., & Machanavajjhala, A. (2009) · now publishers, Inc. eBooks · doi:10.1561/9781601982773 · Cited by 137
Differentially private summaries for sparse data
Cormode, G., Procopiuc, C. M., Srivastava, D., & Tran, T. T. L. (2012) · International Conference on Database Theory · doi:10.1145/2274576.2274608 · Cited by 114
Self-citationCormode, G., & Srivastava, D. (2009) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1559845.1559968 · Cited by 57
Self-citation
Cited by
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
Differential Privacy Techniques for Cyber Physical Systems: A Survey
Hassan, M. U., Rehmani, M. H., & Chen, J. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2019.2944748 · Cited by 564
Differential Privacy for Deep and Federated Learning: A Survey
Ouadrhiri, A. E., & Abdelhadi, A. (2022) · IEEE Access · doi:10.1109/access.2022.3151670 · Cited by 445
A framework for protecting worker location privacy in spatial crowdsourcing
To, H., Ghinita, G., & Shahabi, C. (2014) · Proceedings of the VLDB Endowment · doi:10.14778/2732951.2732966 · Cited by 361
Spatial crowdsourcing: a survey
Tong, Y., Zhou, Z., Zeng, Y., Chen, L., & Shahabi, C. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00568-7 · Cited by 305
Metadata
- Authors
- Cormode, G., Procopiuc, C., Srivastava, D., Shen, E., & Yu, T.
- Venue
- 2012 IEEE 28th International Conference on Data Engineering
- Publisher
- IEEE
- Published
- 2012-04
- Pages
- 20-31
- ISSN
- 1084-4627 (ISSN-L)
- OpenAlex
- W2122290076
- Cited by
- 411
- References
- 30
- FWCI
- 25.11
- Type
- conference paper
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.