research-article

Differentially private hierarchical count-of-counts histograms

Authors:

Ashwin MachanavajjhalaAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 11, Issue 11

Pages 1509 - 1521

https://doi.org/10.14778/3236187.3236202

Published: 01 July 2018 Publication History

Abstract

We consider the problem of privately releasing a class of queries that we call hierarchical count-of-counts histograms. Count-of-counts histograms partition the rows of an input table into groups (e.g., group of people in the same household), and for every integer j report the number of groups of size j. Hierarchical count-of-counts queries report count-of-counts histograms at different granularities as per hierarchy defined on an attribute in the input data (e.g., geographical location of a household at the national, state and county levels). In this paper, we introduce this problem, along with appropriate error metrics and propose a differentially private solution that generates count-of-counts histograms that are consistent across all levels of the hierarchy.

References

[1]

New york city open data. https://opendata.cityofnewyork.us/.

[2]

New york city taxi data. http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml.

[3]

G. Acs, C. Castelluccia, and R. Chen. Differentially private histogram publishing through lossy compression. In ICDM, pages 1--10, 2012.

Digital Library

[4]

R. Barlow, D. Bartholomew, J. Bremner, and H. Brunk. Statistical inference under order restrictions. 1972.

[5]

R. Barlow and H. Brunk. The isotonic regression problem and its dual. Journal of the American Statistical Association, pages 140--147, 1972.

[6]

J. Blocki, A. Datta, and J. Bonneau. Differentially Private Password Frequency Lists. In NDSS '16: The 2016 Network and Distributed System Security Symposium, page 153, February 2016.

[7]

U. C. Bureau. 2010 census summary file 1, 2010 census of population and housing, technical documentation. https: //www.census.gov/prod/cen2010/doc/sf1.pdf, 2012.

[8]

V. R. G. M. C. Li, M. Hay and A. McGregor. Optimizing linear counting queries under differential privacy. In PODS, pages 123--134, 2010.

Digital Library

[9]

K. Chaudhuri, C. Monteleoni, and A. D. Sarwate. Differentially private empirical risk minimization. JMLR, 12:1069--1109, 2011.

Digital Library

[10]

G. Cormode, M. Procopiuc, E. Shen, D. Srivastava, and T. Yu. Differentially private spatial decompositions. In ICDE, pages 20--31, 2012.

Digital Library

[11]

B. Ding, M. Winslett, J. Han, and Z. Li. Differentially private data cubes: optimizing noise sources and consistency. In SIGMOD, pages 217--228, 2011.

Digital Library

[12]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Third Conference on Theory of Cryptography, pages 265--284, 2006.

Digital Library

[13]

A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In STOC, pages 1673--1693, 2009.

Digital Library

[14]

I. Gurobi Optimization. Gurobi optimizer reference manual, 2016.

[15]

M. Hardt, K. Ligett, and F. McSherry. A simple and practical algorithm for differentially private data release. In NIPS, pages 2339--2347, 2012.

Digital Library

[16]

M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boosting the accuracy of differentially private histograms through consistency. PVLDB, 3(1--2):1021--1032, 2010.

Digital Library

[17]

V. Karwa and A. Slavković. Inference using noisy degrees - differentially private synthetic graphs and β models. The Annals of Statistics, (1):87--112, 2016.

[18]

I. Kotsogiannis, A. Machanavajjhala, M. Hay, and G. Miklau. Pythia: Data dependent differentially private algorithm selection. In Proceedings of the 2017 ACM International Conference on Management of Data, pages 1323--1337, 2017.

Digital Library

[19]

C. Li, M. Hay, and G. Miklau. A data- and workload-aware algorithm for range queries under differential privacy. PVLDB, 7(5):341--352, 2014.

Digital Library

[20]

B. Lin and D. Kifer. Information preservation in statistical privacy and bayesian estimation of unattributed histograms. In ACM SIGMOD, pages 677--688, 2013.

Digital Library

[21]

L. Lovasz and M. D. Plummer. Matching Theory. AMS Chelsea Publishing, 1986.

[22]

I. Mironov. On significance of the least significant bits for differential privacy. In Proceedings of the 2012 ACM Conference on Computer and Communications Security, pages 650--661, 2012.

Digital Library

[23]

T. L. N. Li and S. Venkatasubramanian. t-closeness: Privacy beyond k-anonymity and l-diversity. In ICDE, pages 106--115, 2007.

[24]

W. Qardaji, W. Yang, and N. Li. Understanding hierarchical methods for differentially private histograms. PVLDB, 6(14):1954--1965, 2013.

Digital Library

[25]

T. Robertson, P. Waltman, et al. On estimating monotone parameters. The Annals of Mathematical Statistics, pages 1030--1039, 1968.

[26]

Y. Rubner, C. Tomasi, and L. J. Guibas. The earth mover's distance as a metric for image retrieval. Int. J. Comput. Vision, 40(2):99--121, 2000.

Digital Library

[27]

Y. Xiao, L. Xiong, and C. Yuan. Differentially private data release through multidimensional partitioning. In Secure Data Management, pages 150--168, 2010.

[28]

J. Xu, Z. Zhang, X. Xiao, Y. Yang, and G. Yu. Differentially private histogram publication. In ICDE, pages 797--822, 2012.

Digital Library

[29]

J. Zhang, X. Xiao, and X. Xie. Privtree: A differentially private algorithm for hierarchical decompositions. In Proceedings of the 2016 International Conference on Management of Data, pages 155--170, 2016.

Digital Library

[30]

X. Zhang, R. Chen, J. Xu, X. Meng, and Y. Xie. Towards accurate histogram publication under differential privacy. In ICDM, pages 587--595, 2014.

Cited By

Lv CXiao XZhang LYu TQuek TGao DZhou JCardenas A(2024)Publishing Common Neighbors Histograms of Social Networks under Edge Differential PrivacyProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637646(1099-1113)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637646
Alptekin EGursoy M(2023)Building Quadtrees for Spatial Data Under Local Differential PrivacyData and Applications Security and Privacy XXXVII10.1007/978-3-031-37586-6_2(22-39)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37586-6_2
Cao LXiao DYan YMadden SLi G(2021)ATLANTICProceedings of the VLDB Endowment10.14778/3476311.347633714:12(2755-2758)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476337
Show More Cited By

Recommendations

Differentially private anonymized histograms
NIPS'19: Proceedings of the 33rd International Conference on Neural Information Processing Systems

For a dataset of label-count pairs, an anonymized histogram is the multiset of counts. Anonymized histograms appear in various potentially sensitive contexts such as password-frequency lists, degree distribution in social networks, and estimation of ...
Understanding hierarchical methods for differentially private histograms

In recent years, many approaches to differentially privately publish histograms have been proposed. Several approaches rely on constructing tree structures in order to decrease the error when answer large range queries. In this paper, we examine the ...
DPCube: Differentially Private Histogram Release through Multidimensional Partitioning

Differential privacy is a strong notion for protecting individual privacy in privacy preserving data analysis or publishing. In this paper, we study the problem of differentially private histogram release for random workloads. We study two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 11, Issue 11

July 2018

507 pages

ISSN:2150-8097

Editors:
Sihem Amer-Yahia
University of Grenoble Alpes, CNRS
,
Jian Pei
Simon Fraser University

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 July 2018

Published in PVLDB Volume 11, Issue 11

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
76
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lv CXiao XZhang LYu TQuek TGao DZhou JCardenas A(2024)Publishing Common Neighbors Histograms of Social Networks under Edge Differential PrivacyProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637646(1099-1113)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637646
Alptekin EGursoy M(2023)Building Quadtrees for Spatial Data Under Local Differential PrivacyData and Applications Security and Privacy XXXVII10.1007/978-3-031-37586-6_2(22-39)Online publication date: 19-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-37586-6_2
Cao LXiao DYan YMadden SLi G(2021)ATLANTICProceedings of the VLDB Endowment10.14778/3476311.347633714:12(2755-2758)Online publication date: 28-Oct-2021
https://dl.acm.org/doi/10.14778/3476311.3476337
Zheng XYan KDuan JTang WTian L(2021)Histogram Publication over Numerical Values under Local Differential PrivacyWireless Communications & Mobile Computing10.1155/2021/88862552021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8886255
Lu GZheng XDuan JTian LWang X(2021)A Sampling-Based Method for Highly Efficient Privacy-Preserving Data PublicationWireless Communications & Mobile Computing10.1155/2021/66487752021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/6648775
Canonne CKamath GSteinke TLarochelle HRanzato MHadsell RBalcan MLin H(2020)The discrete Gaussian for differential privacyProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3497039(15676-15688)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3497039
Balle BKairouz PMcMahan HThakkar OThakurta ALarochelle HRanzato MHadsell RBalcan MLin H(2020)Privacy amplification via random check-insProceedings of the 34th International Conference on Neural Information Processing Systems10.5555/3495724.3496112(4623-4634)Online publication date: 6-Dec-2020
https://dl.acm.org/doi/10.5555/3495724.3496112
Park YZhong SMozafari BMaier DPottinger RDoan ATan WAlawini ANgo H(2020)QuickSel: Quick Selectivity Learning with Mixture ModelsProceedings of the 2020 ACM SIGMOD International Conference on Management of Data10.1145/3318464.3389727(1017-1033)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3318464.3389727
Uplavikar NVaidya JLin DJiang W(2020)Privacy-Preserving Friend Recommendation in an Integrated Social EnvironmentInformation Systems Security10.1007/978-3-030-65610-2_8(117-136)Online publication date: 16-Dec-2020
https://dl.acm.org/doi/10.1007/978-3-030-65610-2_8
Joseph MKulkarni JMao JWu ZWallach HLarochelle HBeygelzimer Ad'Alché-Buc FFox E(2019)Locally private Gaussian estimationProceedings of the 33rd International Conference on Neural Information Processing Systems10.5555/3454287.3454555(2984-2993)Online publication date: 8-Dec-2019
https://dl.acm.org/doi/10.5555/3454287.3454555

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents