Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model

We thank the reviewer for the thoughtful comments and valuable feedback.

Connections to heavy hitters: We agree that there is a conceptual connection to the heavy hitters problem, as high-frequency elements can be viewed as heavy hitters, especially in the insertion-only setting. However, in the turnstile setting, an element may have high occurrency without being a heavy hitter in the frequency estimation sense: for example, if the element is very frequently added to and removed from the stream. As a result, the goal of our work is different from the heavy hitters problem: we are not trying to identify these high-occurrency elements, but simply to filter them out as items arrive. For this purpose, a simple probabilistic blocklisting approach suffices, and there is no need to apply a heavy hitters algorithm. Moreover, as shown by our lower bound, our blocklisting technique is space-optimal (up to log factors), so the potential improvements from using heavy-hitter algorithms as a form of blocklisting (e.g., use HH algorithms to identify high-occurency algorithms, and treating these as the blocklisted elements) is limited. We will add a discussion to the final version of the paper on the connection of occurrency to the heavy hitters problem, as well as the differences that arise in the turnstile model specifically.

Differences from robust streaming: The problem studied in this work and our approach to solving it are in fact different from the robust streaming literature. Here we highlight these differences in the context of lp-moment estimation. The goal of the robust streaming literature is to design algorithms that can give meaningful utility and (low) space guarantees for lp-moment estimation in the presence of an adaptive adversary, which can generate inputs to the stream based on previous timesteps and feed this to the algorithm in the next timestep. In this model, the algorithm can output an approximation at every timestep, but the output does not need to preserve privacy as in our DP algorithms. In contrast, in the continual release model, the algorithm is required to output a solution at every timestep and these outputs must also preserve DP. As a result, the two problem settings are not comparable and the solution for one problem cannot in general be used to solve the other problem (especially if efficient and accurate solutions are desired).

The DP techniques introduced in [1] and subsequently used in works like [3,4] in the robust streaming literature are different from ours and are intended for a different purpose. Thus it is not possible to directly use prior work in the area to solve our problem (or vice versa). Importantly, the main DP technique introduced by [1] is used to preserve the privacy of the internal randomness of the algorithm, but not to preserve the privacy of the algorithm’s input. As such, these algorithms do not protect the privacy of the user data in input: the adversary can infer information about the user’s data in the input, but is not able to learn about the random bits used (thus making adaptive attacks to the utility of the algorithm harder).

We emphasize that the solutions of [3,4] do not preserve DP at every timestep. For example, [3] devises a solution for lp-moment frequency estimation by separating the cases of when the underlying frequency vector is sparse vs dense. For the sparse case, their algorithm stores the input explicitly using sparse recovery whereas for the dense case they use the DP technique from [1]. Thus for the sparse case, their output is non-private as it is directly computed from the sparse recovery structure.

In contrast, because our goal is to preserve the privacy of the input stream at every timestep, our DP techniques need to differ from the ones used in the robust streaming literature. While we also use sparse recovery tools such as KSET, we must ensure that the output of the KSET does not leak privacy by analyzing its consistency properties (towards sensitivity analysis), and use DP building blocks adapted to our problem such as BM-CountDistinct (Algorithm 5).

Regarding flippancy vs flip number, we emphasize that the concept of flippancy was introduced by [Jain et al] and we show in our work that it may not be a suitable measure to design low space algorithms in the DP turnstile model due to its stateful nature (L91-108), which is the main motivation for introducing occurrency instead. In general, the flip number is a property intrinsic to the problem being computed, while the flippancy (and occurrency) is a property intrinsic to the input stream (regardless of the problem). Thus these two measures are somewhat incomparable.

We thank the reviewer for the detailed comments and valuable feedback.

On using Misra Gries to track elements with high occurrency instead of blocklisting, we note that our algorithm’s goal is not to output elements with high occurrency but simply to filter them out at every timestep. While it is possible to implement a version of the Misra Gries algorithm that continually outputs items with high occurrency, our blocklisting method is simpler as it only involves sampling with a fixed probability.

Thanks for your comment on the use of KSET vs other techniques like IBLT. We have considered using other more complex (and advanced set structures) — it is an interesting direction to pursue, in part because other methods like IBLT can reduce the space used by polylog factors. However, we chose to use KSET because for the DP guarantees, we need to open the black box of the algorithm and analyze its consistency properties (something that is not needed for non-private work). The largely consistent output for KSET in the presence of increased collisions makes it more amenable to analysis in DP settings. We stress that even our use of the simpler to analyze KSET method in the DP setting requires significant care especially when dealing with the failure cases.

Q1: For the comment on the “output being a multiple of a power of 2”, first we observe that actually the output is the product of $2^i$ times a real value (a DP estimate from a count + gaussian noise) so it is not actually an integer power of two (even after rounding). This aspect is however not crucial for the accuracy proof (see below). The scaling up by a factor of $2^i$ is to account for the sampling rate of $2^{-i}$ in the $i$-th stream. In terms of how this relates to our accuracy guarantees (and in particular, our $(1+\eta)$-approximation guarantee), we note that our accuracy guarantee follows from the proof of Lemma A8 in appendix, which shows how our sampling rate is sufficient to give accuracy of the output of the substreams in terms of $(1+\eta)$ multiplicative error plus some additive error. This is because we only need the number of distinct elements in the downsampled stream to be within a multiplicative constant (specifically, 2) range for the concentration bounds to hold with the desired multiplicative approximation and with the allowed additive error. Notice as we discuss in the introduction of our paper, any low-space private algorithm for this problem must incur both multiplicative and additive error.

Q2 & Q3: Regarding the hash functions (and whether they need to be fully random), our construction only requires $\lambda$-wise independent hash functions. Specifically, we use pairwise independent hash functions for the KSET subroutine and $\lambda$-wise independent hash functions for the CountDistinct subroutine. The space complexity for the latter is $O(\lambda \log T)$, which simplifies to $O(polylog(T))$, and thus remains efficient in our setting. We note that using universal hash functions might introduce dependencies as it only ensures low collision probability for any pair of elements, and this may affect utility. In particular, our utility analysis relies on a concentration bound (Lemma D.5) for $\lambda$-wise independent hash functions and thus would need to change if we use universal hash functions instead.

We thank the reviewer for the comment about the subroutines and other technical details of the main algorithm that currently appear in the appendix. Based on this feedback, we plan to reduce the space dedicated to the technical overview (Section 2) in the final version, and instead use the space to incorporate additional core content from the appendix into the main body. We agree with the reviewer’s comment that this would improve readability of the main body. We will also move the definition of \rho-zCDP back to the main text for better clarity of this concept.

As for the significance of the counting problem, we observe that counting serves as a fundamental primitive in the analysis of many private algorithms. Advancements in private counting – especially in the continual release setting – are crucial for the development of private machine learning. For instance, the state-of-the-art differentially private stochastic gradient descent (DP-SGD) underpinning privacy-preserving AI have consistently relied on advances in private sum queries over data streams (including the work on binary tree mechanisms and advanced correlated-noise counting schemes). We believe that foundational research on efficient DP continual release algorithms is necessary for advancing private ML. We observe that the prior work “Counting Distinct Elements in the Turnstile Model with Differential Privacy under Continual Observation” Jain et al. published at NeurIPS 2023, also highlights the relevance and importance of this problem within the machine learning literature.

We thank the reviewer for the thoughtful comments and valuable feedback.

Regarding the comparison against Henzinger, Sricharan, and Steiner (2024), we do, in fact, compare our result to this work in Line 192 of the submitted version; however, we cited an earlier version of the paper, titled "Differentially Private Data Structures under Continual Observation" (2023). We will update the reference to the 2024 version in the final paper for better clarity in the references. We appreciate the reviewer bringing this to our attention.

As for the statement on page 5 of “the space parameter k should be polylog(T)”, we apologize for the typo. More correctly we meant that the space should be sublinear in T, and in our paper it is indeed O(T^{1/3}), and we will make this correction in the final version of the paper.