Conditional Analysis for Key-Value Data with Local Differential Privacy

Jun Zhao; Lin Sun; Shuo Feng; Tao Bai; Teng Wang; Xiaojun Ye

arxiv: 1907.05014 · v1 · pith:PPODT7OEnew · submitted 2019-07-11 · 💻 cs.CR · cs.DB

Conditional Analysis for Key-Value Data with Local Differential Privacy

Lin Sun , Jun Zhao , Xiaojun Ye , Shuo Feng , Teng Wang , Tao Bai This is my paper

Pith reviewed 2026-05-24 23:31 UTC · model grok-4.3

classification 💻 cs.CR cs.DB

keywords local differential privacykey-value dataconditional frequency estimationconditional mean estimationperturbation mechanismsprivacy-preserving data analysis

0 comments

The pith

New perturbation mechanisms for key-value data under local differential privacy enable conditional frequency estimation for keys and conditional mean estimation for values.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops perturbation mechanisms tailored to key-value data that satisfy local differential privacy. From the perturbed outputs it derives estimators for conditional key frequencies and conditional value means. These conditional statistics support downstream tasks that depend on conditional probabilities or marginals. The work extends earlier LDP methods for key-value pairs by adding the conditional analysis layer. Experiments on synthetic and real datasets compare the accuracy of the new estimators against prior approaches.

Core claim

A set of new perturbation mechanisms for key-value data collection and analysis under local differential privacy, together with conditional frequency estimation for key analysis and conditional mean estimation for value analysis, such that the released conditional statistics remain usable for learning tasks.

What carries the argument

Perturbation mechanisms that satisfy local differential privacy on the key-value domain and produce unbiased or bounded-error conditional frequency and mean estimators.

If this is right

The conditional statistics released from the perturbed data can be directly used in machine learning tasks that require conditional probabilities or marginal statistics.
The same perturbation mechanisms support both frequency analysis on keys and mean analysis on values within the same key-value collection.
Accuracy of the conditional estimators can be validated against state-of-the-art competitors on both synthetic and real-world datasets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The conditional estimators could support privacy-preserving conditional queries in NoSQL stores that store key-value records.
The approach may extend to other data types that combine categorical keys with numeric values if similar perturbation primitives are defined.
Downstream models trained on the released conditional statistics would inherit the privacy guarantees without needing access to raw records.

Load-bearing premise

The proposed perturbation mechanisms satisfy local differential privacy for the key-value domain and the conditional estimators derived from the perturbed data remain unbiased or have bounded error under the stated privacy parameters.

What would settle it

An experiment in which the released conditional frequency or mean estimates deviate from the true values by more than the error bound guaranteed by the privacy parameters, or in which the perturbation procedure fails to meet the local differential privacy definition.

Figures

Figures reproduced from arXiv: 1907.05014 by Jun Zhao, Lin Sun, Shuo Feng, Tao Bai, Teng Wang, Xiaojun Ye.

**Figure 1.** Figure 1: Overall results of estimation varying ǫ. VI. ANALYSIS AND EVALUATION In this section, we empirically evaluate the performance of proposed mechanisms. The PrivKV-based mechanisms [12] have shown great advantages in frequency estimation over proposed mechanisms like RAPPOR [6], k-RR [23] and SHist [24]. That is the same in mean estimation, over Harmony [10] and MeanEst [16]. Thus we only compare our propose… view at source ↗

**Figure 2.** Figure 2: Frequency estimation error of different mechanisms [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗

**Figure 3.** Figure 3: Mean estimation error of different mechanisms on Gau [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

**Figure 4.** Figure 4: Estimation error on uniform distribution. [PITH_FULL_IMAGE:figures/full_fig_p011_4.png] view at source ↗

**Figure 5.** Figure 5: F2M under different default values. error of conditional mean estimation is lower to that of conditional mean estimation. We think this is because the error of frequency is involved in the mean estimation, as we analyzed in 1-Way frequency and mean estimation. We also 0.1 0.2 0.4 0.8 1 2 4 5 0.0 0.2 0.4 0.6 0.8 1.0 Average Estimation Error d=2 d=4 d=8 0.1 0.2 0.4 0.8 1 2 4 5 0.0 0.1 0.2 0.3 0.4 0.5 Average… view at source ↗

read the original abstract

Local differential privacy (LDP) has been deemed as the de facto measure for privacy-preserving distributed data collection and analysis. Recently, researchers have extended LDP to the basic data type in NoSQL systems: the key-value data, and show its feasibilities in mean estimation and frequency estimation. In this paper, we develop a set of new perturbation mechanisms for key-value data collection and analysis under the strong model of local differential privacy. Since many modern machine learning tasks rely on the availability of conditional probability or the marginal statistics, we then propose the conditional frequency estimation method for key analysis and the conditional mean estimation for value analysis in key-value data. The released statistics with conditions can further be used in learning tasks. Extensive experiments of frequency and mean estimation on both synthetic and real-world datasets validate the effectiveness and accuracy of the proposed key-value perturbation mechanisms against the state-of-art competitors.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Incremental LDP extension for conditional key-value stats with experiments but thin theoretical detail visible.

read the letter

The core contribution here is a set of perturbation mechanisms for key-value data under local differential privacy, followed by estimators for conditional frequency on keys and conditional mean on values. It builds directly on earlier LDP work for plain frequency and mean estimation in the same data type, then layers on conditioning so the outputs can feed into downstream learning tasks that need marginal or conditional statistics. Experiments on synthetic and real datasets show the new mechanisms beating prior competitors on accuracy for these conditional queries, which is the practical part that lands. That experimental validation is the clearest strength; it demonstrates usability on the target data type without obvious overfitting to one setting. The main limitation is that the abstract supplies no proof sketches, error bounds, or derivation steps for why the mechanisms meet the LDP definition or why the conditional estimators stay unbiased or bounded. Without those, it is difficult to judge whether the central claims hold or whether the conditioning step introduces hidden bias under the privacy budget. The work stays within the established LDP-for-key-value line rather than introducing new primitives or tightening the privacy-utility trade-off in a fundamental way. Readers already working on privacy-preserving collection for NoSQL-style data will find the conditional estimators directly usable if the full proofs check out. It is worth sending to peer review so referees can examine the mechanism definitions and the experimental setup in detail; the topic is narrow but the application area is active enough that a careful check of the math is justified.

Referee Report

1 major / 1 minor

Summary. The manuscript claims to develop a set of new perturbation mechanisms for key-value data collection and analysis under local differential privacy. It proposes the conditional frequency estimation method for key analysis and the conditional mean estimation for value analysis, with the released conditional statistics usable in learning tasks. Extensive experiments on synthetic and real-world datasets are said to validate the effectiveness and accuracy against state-of-the-art competitors.

Significance. If the mechanisms satisfy LDP and the conditional estimators are unbiased with bounded error, the work could meaningfully extend LDP techniques to key-value data common in NoSQL systems and support conditional statistics needed for many ML tasks. The experimental component is a noted strength for empirical validation.

major comments (1)

Abstract: the central claim that the new perturbation mechanisms satisfy the LDP definition and that the derived conditional estimators remain unbiased or have bounded error is presented without any derivation details, error bounds, or proof sketches, which is load-bearing for assessing whether the proposed mechanisms are valid.

minor comments (1)

The abstract refers to 'extensive experiments' validating accuracy but does not name the specific datasets, privacy parameters (e.g., epsilon values), or quantitative metrics used.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and constructive feedback on our manuscript. We address the major comment below.

read point-by-point responses

Referee: [—] Abstract: the central claim that the new perturbation mechanisms satisfy the LDP definition and that the derived conditional estimators remain unbiased or have bounded error is presented without any derivation details, error bounds, or proof sketches, which is load-bearing for assessing whether the proposed mechanisms are valid.

Authors: We note that the abstract is a concise summary of the contributions and is not the appropriate location for detailed derivations or proof sketches, which is standard practice due to length constraints. The full proofs that the perturbation mechanisms satisfy LDP, the derivations establishing unbiasedness of the conditional frequency and mean estimators, and the corresponding error bounds are provided rigorously in the main body of the manuscript. Specifically, the mechanisms and LDP proofs appear in Section 3, the conditional frequency estimation (including unbiasedness and bounds) in Section 4, and the conditional mean estimation in Section 5, supported by theorems and their proofs. If the referee has concerns regarding the validity of these results, we are prepared to expand on any specific aspect. revision: no

Circularity Check

0 steps flagged

No significant circularity; mechanisms and estimators presented as independent contributions

full rationale

The abstract describes development of new LDP perturbation mechanisms for key-value data followed by conditional frequency and mean estimators. No equations, self-citations, or fitted parameters are referenced in a way that would make any claimed result equivalent to its inputs by construction. The work follows the standard pattern of proposing mechanisms and deriving estimators from them, with no load-bearing self-referential steps visible. Central claims remain independent of any prior fitted values or self-citation chains.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, axioms, or invented entities are stated. The implicit assumption that the new mechanisms achieve LDP while preserving utility for conditional queries is treated as a domain assumption pending full text.

pith-pipeline@v0.9.0 · 5683 in / 1048 out tokens · 12896 ms · 2026-05-24T23:31:08.538544+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

27 extracted references · 27 canonical work pages · 2 internal anchors

[1]

Calibrat ing noise to sensitivity in private data analysis,

C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrat ing noise to sensitivity in private data analysis,” in Theory of Cryptography Conference. Springer, 2006, pp. 265–284

work page 2006
[2]

The algorithmic foundations of differential privacy,

C. Dwork, A. Roth et al. , “The algorithmic foundations of differential privacy,” F oundations and Trends® in Theoretical Computer Science , vol. 9, no. 3–4, pp. 211–407, 2014

work page 2014
[3]

PrivTrie: Effective frequent term discovery under local d ifferential privacy,

N. Wang, X. Xiao, Y . Y ang, T. D. Hoang, H. Shin, J. Shin, and G. Y u, “PrivTrie: Effective frequent term discovery under local d ifferential privacy,” inIEEE International Conference on Data Engineering (ICDE) , 2018, pp. 821–832

work page 2018
[4]

Privacy-preserving onl ine task assign- ment in spatial crowdsourcing with untrusted server,

H. To, C. Shahabi, and L. Xiong, “Privacy-preserving onl ine task assign- ment in spatial crowdsourcing with untrusted server,” IEEE International Conference on Data Engineering (ICDE) , pp. 833–844, 2018

work page 2018
[5]

Histogramming pr ivately ever after: Differentially-private data-dependent error boun d optimisation,

M. Fanaeepour and B. I. P . Rubinstein, “Histogramming pr ivately ever after: Differentially-private data-dependent error boun d optimisation,” in IEEE International Conference on Data Engineering (ICDE) , April 2018, pp. 1204–1207

work page 2018
[6]

RAPPOR: Randomiz ed aggregatable privacy-preserving ordinal response,

´U. Erlingsson, V . Pihur, and A. Korolova, “RAPPOR: Randomiz ed aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communicatio ns Security, 2014, pp. 1054–1067

work page 2014
[7]

Learning with privacy at scale,

A. D. P . Team, “Learning with privacy at scale,” https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html, 2017

work page 2017
[8]

Heav y hitter estimation over set-valued data with local differential pr ivacy,

Z. Qin, Y . Y ang, T. Y u, I. Khalil, X. Xiao, and K. Ren, “Heav y hitter estimation over set-valued data with local differential pr ivacy,” in ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 192–203

work page 2016
[9]

Locally differentially priva te frequent itemset mining,

T. Wang, N. Li, and S. Jha, “Locally differentially priva te frequent itemset mining,” in IEEE Symposium on Security and Privacy (SP) , 2018, pp. 127–143

work page 2018
[10]

Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy

T. T. Nguyˆ en, X. Xiao, Y . Y ang, S. C. Hui, H. Shin, and J. S hin, “Collecting and analyzing data from smart device users with local differential privacy,” 2016, http://arxiv.org/abs/1606.05053

work page internal anchor Pith review Pith/arXiv arXiv 2016
[11]

Collecting and analyzing multidimensional data with local differential privacy,

N. Wang, X. Xiao, Y . Y ang, J. Zhao, S. C. Hui, H. Shin, J. Sh in, and G. Y u, “Collecting and analyzing multidimensional data with local differential privacy,” in International Conference on Data Engineering , 2019

work page 2019
[12]

PrivKV: Key-value da ta col- lection with local differential privacy,

Q. Y e, H. Hu, X. Meng, and H. Zheng, “PrivKV: Key-value da ta col- lection with local differential privacy,” in IEEE Symposium on Security and Privacy (SP) , May 2019

work page 2019
[13]

Bias of importance measu res for multi-valued attributes and solutions,

H. Deng, G. Runger, and E. Tuv, “Bias of importance measu res for multi-valued attributes and solutions,” in International Conference on Artiﬁcial Neural Networks . Springer, 2011, pp. 293–300

work page 2011
[14]

Local pr ivacy and statistical minimax rates,

J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local pr ivacy and statistical minimax rates,” in IEEE Annual Symposium on F oundations of Computer Science , 2013, pp. 429–438

work page 2013
[15]

Randomized response: A survey technique for eliminating evasive answer bias,

S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” Journal of the American Statistical Association , vol. 60, no. 309, pp. 63–69, 1965

work page 1965
[16]

Privacy aware learning,

J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Privacy aware learning,” Journal of the ACM (JACM) , vol. 61, no. 6, p. 38, 2014

work page 2014
[17]

Minimax Optimal Procedure s for Locally Private Estimation,

J. C. Duchi and M. I. Jordan, “Minimax Optimal Procedure s for Locally Private Estimation,” Journal of the American Statistical Association , vol. 113, no. 521, pp. 182–201, Jan 2018

work page 2018
[18]

Locally Differentially Private Data Collection and Analysis

T. Wang, J. Zhao, X. Y ang, and X. Ren, “Locally different ially private data collection and analysis,” arXiv preprint arXiv:1906.01777 , 2019

work page internal anchor Pith review Pith/arXiv arXiv 1906
[19]

Locally different ially private pro- tocols for frequency estimation,

T. Wang, J. Blocki, N. Li, and S. Jha, “Locally different ially private pro- tocols for frequency estimation,” in 26th USENIX Security Symposium , 2017, pp. 729–745

work page 2017
[20]

Comparing populat ion means under local differential privacy: with signiﬁcance and pow er,

B. Ding, H. Nori, P . Li, and J. Allen, “Comparing populat ion means under local differential privacy: with signiﬁcance and pow er,” in Thirty- Second AAAI Conference on Artiﬁcial Intelligence , 2018

work page 2018
[21]

Collecting tele metry data privately,

B. Ding, J. Kulkarni, and S. Y ekhanin, “Collecting tele metry data privately,” in Advances in Neural Information Processing Systems , 2017, pp. 3571–3580

work page 2017
[22]

A u tility- optimized framework for personalized private histogram es timation,

Y . Nie, W. Y ang, L. Huang, X. Xie, Z. Zhao, and S. Wang, “A u tility- optimized framework for personalized private histogram es timation,” IEEE Transactions on Knowledge and Data Engineering , vol. 31, no. 4, pp. 655–669, 2019

work page 2019
[23]

Extremal mechanis ms for local differential privacy,

P . Kairouz, S. Oh, and P . Viswanath, “Extremal mechanis ms for local differential privacy,” in Advances in Neural Information Processing Systems, 2014, pp. 2879–2887

work page 2014
[24]

Local, private, efﬁcient prot ocols for succinct histograms,

R. Bassily and A. Smith, “Local, private, efﬁcient prot ocols for succinct histograms,” in Proceedings of the forty-seventh annual ACM symposium on Theory of computing . ACM, 2015, pp. 127–135

work page 2015
[25]

The movielens datasets: History and context,

F. M. Harper and J. A. Konstan, “The movielens datasets: History and context,” Acm transactions on interactive intelligent systems (tiis ), vol. 5, no. 4, p. 19, 2016

work page 2016
[26]

Marginal r elease under local differential privacy,

G. Cormode, T. Kulkarni, and D. Srivastava, “Marginal r elease under local differential privacy,” in ACM International Conference on Manage- ment of Data (SIGMOD) , 2018, pp. 131–146

work page 2018
[27]

P ractical locally private heavy hitters,

R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta, “P ractical locally private heavy hitters,” in Advances in Neural Information Pro- cessing Systems , 2017, pp. 2288–2296. APPENDIX A. Error bound for F2M For the randomized response, assume there are x records with value 1 of N records. For the aggregator, after receiving N records with X records bein...

work page 2017

[1] [1]

Calibrat ing noise to sensitivity in private data analysis,

C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrat ing noise to sensitivity in private data analysis,” in Theory of Cryptography Conference. Springer, 2006, pp. 265–284

work page 2006

[2] [2]

The algorithmic foundations of differential privacy,

C. Dwork, A. Roth et al. , “The algorithmic foundations of differential privacy,” F oundations and Trends® in Theoretical Computer Science , vol. 9, no. 3–4, pp. 211–407, 2014

work page 2014

[3] [3]

PrivTrie: Effective frequent term discovery under local d ifferential privacy,

N. Wang, X. Xiao, Y . Y ang, T. D. Hoang, H. Shin, J. Shin, and G. Y u, “PrivTrie: Effective frequent term discovery under local d ifferential privacy,” inIEEE International Conference on Data Engineering (ICDE) , 2018, pp. 821–832

work page 2018

[4] [4]

Privacy-preserving onl ine task assign- ment in spatial crowdsourcing with untrusted server,

H. To, C. Shahabi, and L. Xiong, “Privacy-preserving onl ine task assign- ment in spatial crowdsourcing with untrusted server,” IEEE International Conference on Data Engineering (ICDE) , pp. 833–844, 2018

work page 2018

[5] [5]

Histogramming pr ivately ever after: Differentially-private data-dependent error boun d optimisation,

M. Fanaeepour and B. I. P . Rubinstein, “Histogramming pr ivately ever after: Differentially-private data-dependent error boun d optimisation,” in IEEE International Conference on Data Engineering (ICDE) , April 2018, pp. 1204–1207

work page 2018

[6] [6]

RAPPOR: Randomiz ed aggregatable privacy-preserving ordinal response,

´U. Erlingsson, V . Pihur, and A. Korolova, “RAPPOR: Randomiz ed aggregatable privacy-preserving ordinal response,” in Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communicatio ns Security, 2014, pp. 1054–1067

work page 2014

[7] [7]

Learning with privacy at scale,

A. D. P . Team, “Learning with privacy at scale,” https://machinelearning.apple.com/2017/12/06/learning-with-privacy-at-scale.html, 2017

work page 2017

[8] [8]

Heav y hitter estimation over set-valued data with local differential pr ivacy,

Z. Qin, Y . Y ang, T. Y u, I. Khalil, X. Xiao, and K. Ren, “Heav y hitter estimation over set-valued data with local differential pr ivacy,” in ACM SIGSAC Conference on Computer and Communications Security , 2016, pp. 192–203

work page 2016

[9] [9]

Locally differentially priva te frequent itemset mining,

T. Wang, N. Li, and S. Jha, “Locally differentially priva te frequent itemset mining,” in IEEE Symposium on Security and Privacy (SP) , 2018, pp. 127–143

work page 2018

[10] [10]

Collecting and Analyzing Data from Smart Device Users with Local Differential Privacy

T. T. Nguyˆ en, X. Xiao, Y . Y ang, S. C. Hui, H. Shin, and J. S hin, “Collecting and analyzing data from smart device users with local differential privacy,” 2016, http://arxiv.org/abs/1606.05053

work page internal anchor Pith review Pith/arXiv arXiv 2016

[11] [11]

Collecting and analyzing multidimensional data with local differential privacy,

N. Wang, X. Xiao, Y . Y ang, J. Zhao, S. C. Hui, H. Shin, J. Sh in, and G. Y u, “Collecting and analyzing multidimensional data with local differential privacy,” in International Conference on Data Engineering , 2019

work page 2019

[12] [12]

PrivKV: Key-value da ta col- lection with local differential privacy,

Q. Y e, H. Hu, X. Meng, and H. Zheng, “PrivKV: Key-value da ta col- lection with local differential privacy,” in IEEE Symposium on Security and Privacy (SP) , May 2019

work page 2019

[13] [13]

Bias of importance measu res for multi-valued attributes and solutions,

H. Deng, G. Runger, and E. Tuv, “Bias of importance measu res for multi-valued attributes and solutions,” in International Conference on Artiﬁcial Neural Networks . Springer, 2011, pp. 293–300

work page 2011

[14] [14]

Local pr ivacy and statistical minimax rates,

J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Local pr ivacy and statistical minimax rates,” in IEEE Annual Symposium on F oundations of Computer Science , 2013, pp. 429–438

work page 2013

[15] [15]

Randomized response: A survey technique for eliminating evasive answer bias,

S. L. Warner, “Randomized response: A survey technique for eliminating evasive answer bias,” Journal of the American Statistical Association , vol. 60, no. 309, pp. 63–69, 1965

work page 1965

[16] [16]

Privacy aware learning,

J. C. Duchi, M. I. Jordan, and M. J. Wainwright, “Privacy aware learning,” Journal of the ACM (JACM) , vol. 61, no. 6, p. 38, 2014

work page 2014

[17] [17]

Minimax Optimal Procedure s for Locally Private Estimation,

J. C. Duchi and M. I. Jordan, “Minimax Optimal Procedure s for Locally Private Estimation,” Journal of the American Statistical Association , vol. 113, no. 521, pp. 182–201, Jan 2018

work page 2018

[18] [18]

Locally Differentially Private Data Collection and Analysis

T. Wang, J. Zhao, X. Y ang, and X. Ren, “Locally different ially private data collection and analysis,” arXiv preprint arXiv:1906.01777 , 2019

work page internal anchor Pith review Pith/arXiv arXiv 1906

[19] [19]

Locally different ially private pro- tocols for frequency estimation,

T. Wang, J. Blocki, N. Li, and S. Jha, “Locally different ially private pro- tocols for frequency estimation,” in 26th USENIX Security Symposium , 2017, pp. 729–745

work page 2017

[20] [20]

Comparing populat ion means under local differential privacy: with signiﬁcance and pow er,

B. Ding, H. Nori, P . Li, and J. Allen, “Comparing populat ion means under local differential privacy: with signiﬁcance and pow er,” in Thirty- Second AAAI Conference on Artiﬁcial Intelligence , 2018

work page 2018

[21] [21]

Collecting tele metry data privately,

B. Ding, J. Kulkarni, and S. Y ekhanin, “Collecting tele metry data privately,” in Advances in Neural Information Processing Systems , 2017, pp. 3571–3580

work page 2017

[22] [22]

A u tility- optimized framework for personalized private histogram es timation,

Y . Nie, W. Y ang, L. Huang, X. Xie, Z. Zhao, and S. Wang, “A u tility- optimized framework for personalized private histogram es timation,” IEEE Transactions on Knowledge and Data Engineering , vol. 31, no. 4, pp. 655–669, 2019

work page 2019

[23] [23]

Extremal mechanis ms for local differential privacy,

P . Kairouz, S. Oh, and P . Viswanath, “Extremal mechanis ms for local differential privacy,” in Advances in Neural Information Processing Systems, 2014, pp. 2879–2887

work page 2014

[24] [24]

Local, private, efﬁcient prot ocols for succinct histograms,

R. Bassily and A. Smith, “Local, private, efﬁcient prot ocols for succinct histograms,” in Proceedings of the forty-seventh annual ACM symposium on Theory of computing . ACM, 2015, pp. 127–135

work page 2015

[25] [25]

The movielens datasets: History and context,

F. M. Harper and J. A. Konstan, “The movielens datasets: History and context,” Acm transactions on interactive intelligent systems (tiis ), vol. 5, no. 4, p. 19, 2016

work page 2016

[26] [26]

Marginal r elease under local differential privacy,

G. Cormode, T. Kulkarni, and D. Srivastava, “Marginal r elease under local differential privacy,” in ACM International Conference on Manage- ment of Data (SIGMOD) , 2018, pp. 131–146

work page 2018

[27] [27]

P ractical locally private heavy hitters,

R. Bassily, K. Nissim, U. Stemmer, and A. G. Thakurta, “P ractical locally private heavy hitters,” in Advances in Neural Information Pro- cessing Systems , 2017, pp. 2288–2296. APPENDIX A. Error bound for F2M For the randomized response, assume there are x records with value 1 of N records. For the aggregator, after receiving N records with X records bein...

work page 2017