pith. sign in

arxiv: 2606.11760 · v1 · pith:S7R5OMUHnew · submitted 2026-06-10 · 💻 cs.DS · cs.CR· cs.DB

A Fast Gaussian Mechanism under Continual Observation, with Applications

Rasmus Pagh , Sia Sejer This is my paper

Pith reviewed 2026-06-27 08:20 UTC · model grok-4.3

classification 💻 cs.DS cs.CRcs.DB
keywords continual observationdifferential privacyGaussian mechanismbinary tree mechanismBrownian bridgesprivate sketchingrange countingjoin size estimation
0
0 comments X

The pith

A data structure using Brownian bridges samples any entry of the binary tree Gaussian noise vector in constant time while matching the exact distribution.

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

The paper addresses continual private release of vector sums where only subsets of entries are needed at each time step. It establishes a method to generate noise matching the binary tree mechanism exactly, but at constant time per sample instead of O(log T). The approach relies on a new data structure that generates correlated Gaussian values via Brownian bridges. This enables faster computation for private sketching applications while preserving the privacy guarantees of the original mechanism.

Core claim

It is possible to sample any desired entry in a given noise vector in constant time while reproducing exactly the distribution of the binary tree mechanism with Gaussian noise. The improvement on the known time bound of O(log T) comes from a new data structure that allows us to sample a new noise value with the correct correlations in constant time using Brownian bridges.

What carries the argument

Brownian bridge data structure for constant-time sampling of correlated noise values matching the binary tree mechanism.

If this is right

  • Yields a dynamic data structure for orthogonal range counting queries with improved privacy/accuracy/space trade-off over prior work.
  • Enables join size estimation via differentially private CountSketches with improved high-probability bounds.
  • Reduces the per-update cost for releasing subsets of entries in continual observation from O(k log T) to O(k) in the worst case when k entries are queried.

Where Pith is reading between the lines

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

  • The constant-time sampling could be composed with other noise mechanisms that rely on prefix-sum correlations in streaming settings.
  • The technique may allow continual observation mechanisms to handle much larger time horizons T without the logarithmic sampling bottleneck becoming the dominant cost.
  • Applications that already use CountSketch could adopt the structure to obtain tighter concentration bounds without increasing privacy loss.

Load-bearing premise

The Brownian bridge construction exactly maintains the joint distribution and correlations of the binary tree mechanism without bias or added error.

What would settle it

Compute the empirical covariance of many samples drawn from the new structure for a fixed small T and compare it entrywise to the covariance matrix implied by the binary tree mechanism; any systematic deviation would falsify exact distribution matching.

Figures

Figures reproduced from arXiv: 2606.11760 by Rasmus Pagh, Sia Sejer.

Figure 1
Figure 1. Figure 1: Overview of results on dynamic private orthogonal range counting with [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Factorization with reconstruction matrix [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An example of the structure saved for each index [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Overview of results on static private orthogonal range counting for a set of [PITH_FULL_IMAGE:figures/full_fig_p023_4.png] view at source ↗
read the original abstract

We consider the problem of privately releasing a $k$-dimensional vector under updates: Starting with a zero vector, at times $t_1, t_2,\dots$ the vector is updated by adding $x^{(1)}, x^{(2)},\dots$, respectively. For positive integers $T$, $k$ we model the updates as a data set $\{(t_i, x^{(i)})\}_i$, where $t_i \in [T]$ and $x^{(i)} \in B_k$ (the $k$-dimensional unit ball). Two such data sets are said to be neighboring if their symmetric difference has size at most $1$. The continual release consists of the sum $A^{(t)} = \sum_{i \; : \; t_i \leq t} x^{(i)}$ for each time step $t=1,\dots,T$. Classical continual release techniques allow us to release an approximation of $A^{(1)},\dots,A^{(T)}$ with additive noise of magnitude $\text{polylog}(T)$, computed in time $O(kT)$, even in the on-line, adaptive case where data is continually revealed for the current time step. Motivated by private sketching techniques, we consider the setting where only a \emph{subset} of entries in $A^{(t)}$ need to be released at time step $t$. Our new result is that it is possible to sample any desired entry in a given noise vector in \emph{constant time} while reproducing exactly the distribution of the binary tree mechanism with Gaussian noise. The improvement on the known time bound of $O(\log T)$ comes from a new data structure that allows us to sample a new noise value with the correct correlations in constant time using Brownian bridges. We present two data management applications, of independent interest, that use our technique in conjunction with differentially private CountSketches: 1) A dynamic data structure for orthogonal range counting queries with a better privacy/accuracy/space trade-off than previous data structures, and 2) Join size estimation, where in addition we show improved high-probability bounds.

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.

Referee Report

1 major / 2 minor

Summary. The paper claims a data structure for the Gaussian mechanism under continual observation that samples any desired coordinate of the noise vector in O(1) time while exactly reproducing the joint distribution of the standard binary-tree mechanism (independent Gaussians at dyadic nodes with level-dependent variances). The construction uses Brownian bridges to generate the required correlations on demand. Two applications to differentially private CountSketches are presented: improved orthogonal range counting and join-size estimation with better privacy/accuracy/space trade-offs.

Significance. If the exact distributional equivalence is established, the O(1) sampling time would remove the O(log T) bottleneck in continual-release mechanisms, enabling more efficient private dynamic data structures at scale. The applications demonstrate concrete utility gains when combined with sketching.

major comments (1)
  1. [Abstract / data-structure construction] Abstract and the Brownian-bridge construction: the central claim of exact reproduction of the binary-tree Gaussian distribution requires a proof that the covariance for every pair of times t,s matches the discrete dyadic sum structure (noise at t is sum of O(log T) independent Gaussians whose variances depend on the binary decomposition of t). The continuous Brownian-bridge covariance min(s,t) is not obviously identical; if they differ, both the constant-time claim and the inherited (ε,δ)-DP parameters are invalidated. This is load-bearing for the main result.
minor comments (2)
  1. [Abstract] The abstract states the noise magnitude is polylog(T) but does not give the precise dependence on T, k, or the privacy parameters; add an explicit statement in the introduction or theorem statement.
  2. [Applications] The applications section should include a direct comparison table against prior continual-release CountSketch constructions (time, space, error, privacy) to substantiate the claimed improvements.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and for identifying the need to explicitly verify the covariance structure. We address the concern regarding exact distributional equivalence below. We will revise the manuscript to include a dedicated proof of the covariance match.

read point-by-point responses

  1. Referee: [Abstract / data-structure construction] Abstract and the Brownian-bridge construction: the central claim of exact reproduction of the binary-tree Gaussian distribution requires a proof that the covariance for every pair of times t,s matches the discrete dyadic sum structure (noise at t is sum of O(log T) independent Gaussians whose variances depend on the binary decomposition of t). The continuous Brownian-bridge covariance min(s,t) is not obviously identical; if they differ, both the constant-time claim and the inherited (ε,δ)-DP parameters are invalidated. This is load-bearing for the main result.

    Authors: We thank the referee for highlighting this critical point. The construction does not apply a standard Brownian bridge with covariance min(s,t) directly to the interval [1,T]. Instead, Section 3 employs a recursive, hierarchical Brownian bridge aligned with the binary tree: at each dyadic level l, an independent Brownian bridge (scaled by the level-specific variance σ_l²) is used to generate the incremental noise contribution over the corresponding interval. This ensures that for any pair t,s the resulting covariance equals exactly the sum of σ_l² over all levels l where the binary representations of t and s share the same ancestor node. We will add an explicit lemma (new Lemma 3.3) that derives Cov(Z_t, Z_s) = ∑_{l : bit_l(t)=bit_l(s)} σ_l² and shows this matches the standard binary-tree mechanism. Consequently the joint distribution, the O(1) sampling time, and the inherited (ε,δ)-DP parameters remain valid. The revision will make this equivalence fully rigorous without changing any claims. revision: yes

Circularity Check

0 steps flagged

No circularity; derivation is self-contained via new construction

full rationale

The paper presents a novel data structure for constant-time sampling of noise entries that exactly reproduces the binary-tree Gaussian mechanism distribution, using Brownian bridges for correlations. No steps reduce by construction to fitted inputs, self-definitions, or load-bearing self-citations; the central claim is a new algorithmic technique whose correctness is asserted via explicit distributional equivalence rather than renaming or importing unverified uniqueness results. The provided abstract and description contain no equations or citations that exhibit the enumerated circular patterns. This is the expected outcome for a paper whose contribution is an independent algorithmic improvement.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

No free parameters, axioms, or invented entities are identifiable from the abstract alone; the work builds on the existing binary tree mechanism and Gaussian noise without introducing new fitted quantities or entities.

pith-pipeline@v0.9.1-grok · 5928 in / 1155 out tokens · 27675 ms · 2026-06-27T08:20:27.658291+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 31 canonical work pages · 1 internal anchor

  1. [1]

    Hierarchical categories in colored searching

    Peyman Afshani, Rasmus Killmann, and Kasper Green Larsen. Hierarchical categories in colored searching. In Sang Won Bae and Heejin Park, editors,33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:15, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibn...

    work page doi:10.4230/lipics.isaac.2022.25 2022

  2. [2]

    Gibbons, Yossi Matias, and Mario Szegedy

    Noga Alon, Phillip B. Gibbons, Yossi Matias, and Mario Szegedy. Tracking join and self-join sizes in limited storage. InProceedings of the Eighteenth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 10–20, 1999. doi: 10.1145/303976.303978

    work page doi:10.1145/303976.303978 1999

  3. [3]

    A smooth binary mechanism for efficient private continual observation

    Joel Daniel Andersson and Rasmus Pagh. A smooth binary mechanism for efficient private continual observation. InAdvances in Neural Information Processing Systems, volume 36, pages 49133–49145. Curran Associates, Inc., 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/99c41fb9fd53abfdd4a0259560ef1c9d-Paper-Conference. pdf

    2023

  4. [4]

    Improved counting under continual observation with pure differential privacy.CoRR, abs/2408.07021, 2024

    Joel Daniel Andersson, Rasmus Pagh, and Sahel Torkamani. Improved counting under continual observation with pure differential privacy.CoRR, abs/2408.07021, 2024. doi: 10.48550/arXiv.2408.07021. URL https://doi.org/10.48550/ arXiv.2408.07021

    work page doi:10.48550/arxiv.2408.07021 2024

  5. [5]

    Private lossless multiple release

    Joel Daniel Andersson, Lukas Retschmeier, Boel Nelson, and Rasmus Pagh. Private lossless multiple release. In Proceedings of 42nd International Conference on Machine Learning (ICML), ICML’25. JMLR.org, 2025

    2025

  6. [6]

    Representing sparse vectors with differential privacy, low error, optimal space, and fast access.Journal of Privacy and Confidentiality, 12(2), 2022

    Martin Aumüller, Christian Janos Lebeda, and Rasmus Pagh. Representing sparse vectors with differential privacy, low error, optimal space, and fast access.Journal of Privacy and Confidentiality, 12(2), 2022. doi: 10.29012/jpc.809

    work page doi:10.29012/jpc.809 2022

  7. [7]

    Proceedings, Part I, of the 14th International Conference on Theory of Cryptography - Volume 9985 , publisher =

    Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors,Theory of Cryptography, pages 635–658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. ISBN 978-3-662-53641-4. doi: 10.1007/978-3-662-53641-4_24

    work page doi:10.1007/978-3-662-53641-4_24 2016

  8. [8]

    The discrete Gaussian for differential privacy.Journal of Privacy and Confidentiality, 12(1), July 2022

    Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy.Journal of Privacy and Confidentiality, 12(1), July 2022. doi: 10.29012/jpc.784. URL https://journalprivacyconfidentiality.org/index. php/jpc/article/view/784

    work page doi:10.29012/jpc.784 2022

  9. [9]

    Hubert Chan, Elaine Shi, and Dawn Song

    T.-H. Hubert Chan, Elaine Shi, and Dawn Song. Private and continual release of statistics.ACM Trans. Inf. Syst. Secur., 14(3), nov 2011. ISSN 1094-9224. doi: 10.1145/2043621.2043626. URL https://doi.org/10.1145/2043621.2043626. Appeared in Cryptology ePrint Archive 2010/076 and ICALP 2010

    work page doi:10.1145/2043621.2043626 2011

  10. [10]

    Timothy M. Chan. Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range Trees Strike Back. In Boris Aronov and Matthew J. Katz, editors,33rd International Symposium on Computational Geometry (SoCG 2017), volume 77 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 27:1–27:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leib...

    work page doi:10.4230/lipics.socg.2017.27 2017

  11. [11]

    Finding frequent items in data streams.Theoretical Computer Science, 312(1):3–15, 2004

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams.Theoretical Computer Science, 312(1):3–15, 2004. ISSN 0304-3975. doi: 10.1016/S0304-3975(03)00400-6. URL https://doi.org/10.1016/S0304- 3975(03)00400-6. Conference version in ICALP 2002

    work page doi:10.1016/s0304-3975(03)00400-6 2004

  12. [12]

    Differentially private weighted sampling

    Edith Cohen, Ofir Geri, Tamás Sarlós, and Uri Stemmer. Differentially private weighted sampling. InProceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 130 ofProceedings of Machine Learning Research, pages 3068–3076. PMLR, 2021. URL https://proceedings.mlr.press/v130/cohen21b.html

    2021

  13. [13]

    Differentially private summaries for sparse data

    Graham Cormode, Cecilia Procopiuc, Divesh Srivastava, and Thanh TL Tran. Differentially private summaries for sparse data. InProceedings of the 15th International Conference on Database Theory, pages 299–311, 2012. doi: 10.1145/2274576.2274608

    work page doi:10.1145/2274576.2274608 2012

  14. [14]

    A Dense Model Theorem for the Boolean Slice

    Krishnamurthy Dj Dvijotham, H. Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta. Efficient and near-optimal noise generation for streaming differential privacy. In65th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2024, Chicago, IL, USA, October 27-30, 2024, pages 2306–2317. IEEE, 2024. doi: 10.1109/FOCS61266.2024...

    work page doi:10.1109/focs61266.2024.00135 2024

  15. [15]

    The algorithmic foundations of differential privacy.Found

    Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy.Found. Trends Theor. Comput. Sci., 9(3-4):211–407, aug 2014. ISSN 1551-305X. doi: 10.1561/0400000042. URL https://doi.org/10.1561/0400000042

    work page doi:10.1561/0400000042 2014

  16. [16]

    Rothblum

    Cynthia Dwork, Moni Naor, Toniann Pitassi, and Guy N. Rothblum. Differential privacy under continual observation. STOC, 2010. doi: 10.1145/1806689.1806787. URL https://doi.org/10.1145/1806689.1806787

    work page doi:10.1145/1806689.1806787 2010

  17. [17]

    Rothblum

    Cynthia Dwork, Moni Naor, Omer Reingold, and Guy N. Rothblum. Pure differential privacy for rectangle queries via private partitions. InAdvances in Cryptology – ASIACRYPT 2015, volume 9453, pages 735–751, Berlin, Heidelberg,

    2015

  18. [18]

    ISBN 978-3-662-48800-3

    Springer Berlin Heidelberg. ISBN 978-3-662-48800-3. doi: 10.1007/978-3-662-48800-3\_30. URL https://doi.org/ 10.1007/978-3-662-48800-3_30

    work page doi:10.1007/978-3-662-48800-3

  19. [19]

    Differentially private continual releases of streaming frequency moment estimations

    Alessandro Epasto, Jieming Mao, Andres Munoz Medina, Vahab Mirrokni, Sergei Vassilvitskii, and Peilin Zhong. Differentially private continual releases of streaming frequency moment estimations. In Yael Tauman Kalai, editor, A Fast Gaussian Mechanism under Continual Observation, with Applications 17 14th Innovations in Theoretical Computer Science Conferen...

    work page doi:10.4230/lipics.itcs.2023.48 2023

  20. [20]

    Foucart and H

    Simon Foucart and Holger Rauhut.A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, 2013. ISBN 978-0-8176-4947-0. doi: 10.1007/978-0-8176-4948-7. URL https://doi.org/ 10.1007/978-0-8176-4948-7

    work page doi:10.1007/978-0-8176-4948-7 2013

  21. [21]

    Almost tight error bounds on differentially private continual counting

    Monika Henzinger, Jalaj Upadhyay, and Sarvagya Upadhyay. Almost tight error bounds on differentially private continual counting. InProceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 5003–5039, 2023. doi: 10.1137/1.9781611977554.ch183. URL https://doi.org/10.1137/1.9781611977554.ch183

    work page doi:10.1137/1.9781611977554.ch183 2023

  22. [22]

    Sparse dimensionality reduction revisited

    Mikael Møller Høgsgaard, Lior Kamma, Kasper Green Larsen, Jelani Nelson, and Chris Schwiegelshohn. Sparse dimensionality reduction revisited. InProceedings of the 41st International Conference on Machine Learning (ICML), pages 18454–18469, 2024. URL https://proceedings.mlr.press/v235/hogsgaard24a.html

    2024

  23. [23]

    Scalable differentially private sketches under continual observation.CoRR, abs/2507.03361, 2025

    Rayne Holland. Scalable differentially private sketches under continual observation.CoRR, abs/2507.03361, 2025. doi: 10.48550/arXiv.2507.03361. URL https://doi.org/10.48550/arXiv.2507.03361

    work page doi:10.48550/arxiv.2507.03361 2025

  24. [24]

    Efficient use of differentially private binary trees.Theory and Practice of Differential Privacy (TPDP), 2: 26–27, 2015

    James Honaker. Efficient use of differentially private binary trees.Theory and Practice of Differential Privacy (TPDP), 2: 26–27, 2015

    2015

  25. [25]

    Releasing search queries and clicks privately

    Aleksandra Korolova, Krishnaram Kenthapadi, Nina Mishra, and Alexandros Ntoulas. Releasing search queries and clicks privately. InProceedings of the 18th international conference on World Wide Web (WWW), pages 171–180, 2009. doi: 10.1145/1526709.1526733

    work page doi:10.1145/1526709.1526733 2009

  26. [26]

    PrivateSQL: a differentially private sql query engine.Proceedings of the VLDB Endowment, 12(11):1371–1384,

    Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. PrivateSQL: a differentially private sql query engine.Proceedings of the VLDB Endowment, 12(11):1371–1384,

  27. [27]

    doi: 10.14778/3342263.3342274

    work page doi:10.14778/3342263.3342274

  28. [28]

    Fragkiskos Koufogiannis, Shuo Han, and George J. Pappas. Gradual release of sensitive data under differen- tial privacy.Journal of Privacy and Confidentiality, 7(2), Jan. 2017. doi: 10.29012/jpc.v7i2.649. URL https: //journalprivacyconfidentiality.org/index.php/jpc/article/view/649

    work page doi:10.29012/jpc.v7i2.649 2017

  29. [29]

    Countsketches, feature hashing and the median of three

    Kasper Green Larsen, Rasmus Pagh, and Jakub Tetěk. Countsketches, feature hashing and the median of three. InProceedings of the 38th International Conference on Machine Learning (ICML), pages 6011–6020, 2021. URL http: //proceedings.mlr.press/v139/larsen21a.html

    2021

  30. [30]

    Better differentially private approximate histograms and heavy hitters using the Misra-Gries sketch.ACM Transactions on Database Systems, 50(3):9:1–9:26, 2025

    Christian Janos Lebeda and Jakub Tetěk. Better differentially private approximate histograms and heavy hitters using the Misra-Gries sketch.ACM Transactions on Database Systems, 50(3):9:1–9:26, 2025. doi: 10.1145/3716375. URL https://doi.org/10.1145/3716375

    work page doi:10.1145/3716375 2025

  31. [31]

    The matrix mechanism: optimizing linear counting queries under differential privacy.The VLDB journal, 24(6):757–781, 2015

    Chao Li, Gerome Miklau, Michael Hay, Andrew McGregor, and Vibhor Rastogi. The matrix mechanism: optimizing linear counting queries under differential privacy.The VLDB journal, 24(6):757–781, 2015. doi: 10.1007/s00778-015- 0398-x

    work page doi:10.1007/s00778-015- 2015

  32. [32]

    Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020(3):751–780, 2020

    Jiřı Matoušek, Aleksandar Nikolov, and Kunal Talwar. Factorization norms and hereditary discrepancy.International Mathematics Research Notices, 2020(3):751–780, 2020. doi: 10.1093/imrn/rny033. URL https://doi.org/10.1093/imrn/ rny033

    work page doi:10.1093/imrn/rny033 2020

  33. [33]

    Minton and Eric Price

    Gregory T. Minton and Eric Price. Improved concentration bounds for count-sketch. InProceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 669–686, 2014. doi: 10.1137/1.9781611973402.51. URL https://epubs.siam.org/doi/abs/10.1137/1.9781611973402.51

    work page doi:10.1137/1.9781611973402.51 2014

  34. [34]

    Darakhshan J. Mir, S. Muthukrishnan, Aleksandar Nikolov, and Rebecca N. Wright. Pan-private algorithms via statistics on sketches. InProceedings of the Thirtieth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 37–48, 2011. doi: 10.1145/1989284.1989290. URL https://doi.org/10.1145/1989284.1989290

    work page doi:10.1145/1989284.1989290 2011

  35. [35]

    Optimal private halfspace counting via discrepancy

    Shanmugavelayutham Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. InProceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1285–1292, 2012. doi: 10.1145/2213977.2214090. URL https://doi.org/10.1145/2213977.2214090

    work page doi:10.1145/2213977.2214090 2012

  36. [36]

    Improved utility analysis of private countsketch

    Rasmus Pagh and Mikkel Thorup. Improved utility analysis of private countsketch. InAdvances in Neural Information Processing Systems (NeurIPS), volume 35, pages 25631–25643. Curran Associates, Inc., 2022. URL https://proceedings. neurips.cc/paper_files/paper/2022/file/a47f5cdff1469751597d78e803fc590f-Paper-Conference.pdf

    2022

  37. [37]

    Differential privacy on fully dynamic streams

    Yuan Qiu and Ke Yi. Differential privacy on fully dynamic streams. InAdvances in Neural Information Processing Systems (NeurIPS), 2025

    2025

  38. [38]

    Improved differentially private euclidean distance approximation

    Nina Mesing Stausholm. Improved differentially private euclidean distance approximation. InProceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS), pages 42–56, 2021. doi: 10.1145/3452021.3458328

    work page doi:10.1145/3452021.3458328 2021

  39. [39]

    Feature hashing for large scale multitask learning

    Kilian Weinberger, Anirban Dasgupta, John Langford, Alex Smola, and Josh Attenberg. Feature hashing for large scale multitask learning. InProceedings of the 26th International Conference on Machine Learning (ICML), pages 1113–1120, 18 Rasmus Pagh and Sia Sejer

  40. [40]

    doi: 10.1145/1553374.1553516

    work page doi:10.1145/1553374.1553516

  41. [41]

    Differential Privacy via Wavelet Transforms

    Xiaokui Xiao, Guozhang Wang, and Johannes Gehrke. Differential privacy via wavelet transforms.IEEE Transactions on Knowledge and Data Engineering, 23(8):1200–1214, 2011. doi: 10.1109/TKDE.2010.247. URL https://doi.org/10.1109/ TKDE.2010.247. Appeared as arXiv 0909.5530 and in ICDE 2010

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/tkde.2010.247 2011

  42. [42]

    Cagra: Highly parallel graph construction and approximate nearest neighbor search for gpus,

    Meifan Zhang, Xin Liu, and Lihua Yin. Sketches-based join size estimation under local differential privacy. In Proceedings of the 40th IEEE International Conference on Data Engineering (ICDE), pages 1726–1738. IEEE, 2024. doi: 10.1109/ICDE60146.2024.00140. URL https://doi.org/10.1109/ICDE60146.2024.00140

    work page doi:10.1109/icde60146.2024.00140 2024

  43. [43]

    Differentially private linear sketches: Efficient implementations and applications

    Fuheng Zhao, Dan Qiao, Rachel Redberg, Divyakant Agrawal, Amr El Abbadi, and Yu-Xiang Wang. Differentially private linear sketches: Efficient implementations and applications. InAdvances in Neural Information Processing Systems (NeurIPS), 2022. URL http://papers.nips.cc/paper_files/paper/2022/hash/525338e0d98401a62950bc7c454eb83d- Abstract-Conference.html...

    2022

  44. [45]

    𝜀-DP (log𝐵) 1.5𝑑+1/𝜀 𝐵𝑑

  45. [46]

    𝜀-DP (log(𝐵) + (log𝑛) 1.5𝑑+2)/𝜀 𝑛𝑑 (log𝑛) 2𝑑+1 log(𝐵)/𝜀 𝑛(log𝑛) 𝑑

  46. [47]

    ∑︁ 𝑖 𝑋𝑖 ≥𝐾 # ≤ ∑︁ 𝑖 Pr [|𝑋𝑖 |>𝜎 ] +Pr

    + [30] (𝜀, 1 100 )-DP Ω(log𝑛) 𝑑−1 /𝜀 anyΩ(log𝐵) 𝑑−1 /𝜀 This paper 𝜀2/2-zCDP 𝐸≥ (log𝐵) 𝑑+2 /𝜀 𝑛(log𝐵) 𝑑+1 /𝐸 Fig. 4. Overview of results on static private orthogonal range counting for a set of 𝑛 points in [𝐵] 𝑑. Lower bounds in terms of 𝑛 and 𝐵, for worst-case inputs and no restriction on the other parameter, are shown with red background, and hold in par...