On Fine-Grained Distinct Element Estimation

We thank the reviewer for their feedback and constructive criticism.

Mridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, Sourav Chakraborty: Improved Streaming Algorithm for the Klee's Measure Problem and Generalizations. APPROX/RANDOM 2024

It also uses subsampling as opposed to sketching ideas for distinct elements.

Thank you for pointing out this reference. We have added a reference as an additional work that uses subsampling.

I think that the algorithm would be a lot more convincing if it recovered the worst case bounds, or were at least competitive with the worst case algorthms without the assumption that $\beta$ is small. Additonally, most beyond worst case results analyze an algorithm that is already widely used. In this case a worst-case performance is not good and the algorithm is designed from scratch.

We emphasize that our bounds are competitive with the worst case bounds. We can further optimize the $O(\alpha\log n\log\log n)$ term to $O(\alpha\log n)$ by referencing an existing technique instead of Algorithm 1, so that overall the only difference between our bounds and the worst-case bounds is the $O(\log n)$ communication required by sending the identity of each sample.

On the other hand, many datasets often exhibit some sort of skewed distribution and our results show that the communication can be significantly improved upon known bounds in these settings.

The modelling of the problem and determining the parameterization in terms of $\beta$ has value. Unfortunately, the ideas themselves and the analysis is not too novel. The techniques have been around for quite a while and while piecing them together is not trivial, I also did not feel like I learned much when reading this paper.

We acknowledge that the core techniques used (e.g., subsampling, sketching primitives adapted for communication) are built upon existing foundational work in streaming and communication complexity. However, we believe the novelty lies in: 1) Identifying the collision parameter C/β as the key factor governing complexity beyond the worst case. 2) Designing protocols specifically tailored to leverage this parameter. 3) Providing a complete analysis including matching upper and lower bounds in this parameterized setting, which requires non-trivial adaptation and combination of existing techniques. While the tools may be familiar, establishing the tight parameterized complexity is our core technical contribution. We would also like to highlight novel techniques, such as using robust statistics to achieve our streaming algorithm for distinct elements, which allows for accurate estimation even in the presence of adversarial noise and memory constraints; to the best of our knowledge, no prior results utilize robust statistics for distinct element estimation in the streaming setting.

Additionally, although there is a decent body of literature on distributional assumptions and fine-grained complexity, surprisingly there is comparatively much less literature for sublinear algorithms. In particular, there has recently been a number of works in the area of learning-augmented algorithms that specifically use distributional assumptions in addition to machine-learning advice to achieve better guarantees. Thus although distributional assumptions have been studied in the past, we respectfully believe there is value in exploring these directions in new areas, particularly for the purposes of bridging practical algorithms and impossibility results in theory.

We thank the reviewer for their positive assessment and thoughtful questions.

The problem itself also seems well-studied, although I am wondering whether it is still relevant in contemporary ML applications. If the authors are aware of more recent applications of the problem in ML, they are welcome to provide some.

Thank you for this question. While Distributed Distinct Elements is a classic problem, variations and related counting/frequency estimation tasks remain highly relevant in modern large-scale ML and data analysis. Examples include: estimating cardinalities in federated learning settings without sharing raw data, analyzing feature overlap or user reach across distributed datasets/services, monitoring network traffic statistics (unique flows/IPs), and estimating distinct items in large graphs or databases distributed across clusters. We will add references or discussion points highlighting these contemporary ML applications in the revised introduction or related work.

In the algorithmic contributions (Theorem 1.1 and 1.2), what would happen if we mis-estimated the number of collisions? In other words, is there any way of using the obtained results when one is not certain about the number of collisions (e.g., can one "test" different choices)?

Our algorithm is fairly robust, as the error in the estimate for the number of collisions can be translated to an additional number of samples and thus communication. For instance, if the estimate is incorrect by a $O(\log n)$ factor, we can still handle this using an extra $O(\log n)$ factor in the communication. In general, if $\beta$ is underestimated, the protocol's correctness guarantee may fail. If $\beta$ is overestimated, the protocol remains correct but uses more communication than necessary. On the other hand, it's not quite clear how to test different choices, because an incorrect choice could erroneously lead to an estimate that "looks" correct for the incorrect choice.

We thank the reviewer for their positive feedback and the pertinent question regarding Algorithm 1.

Is Algorithm 1 necessary? As stated in Line 58 on Page 2, a one-pass streaming algorithm for distinct element estimation can be transformed into the distributed setting, yielding a protocol with $O(\alpha/\epsilon^2 +\alpha\log n)$ bits of communication.

Since Algorithm 1 aims for a constant-factor approximation of the number of distinct elements, one could instead apply the aforementioned protocol, achieving a communication cost of $O(\alpha +\alpha\log n)$, which appears lower than that of Algorithm 1.

This is a great point. We originally had Algorithm 1 as a warm-up to the main results in Algorithm 2 and Algorithm 3 because both the algorithmic structure and the corresponding analysis are similar but simpler. However, given the additional $\log\log n$ factor incurred by Algorithm 1, we agree that it would be better to simply reference an existing protocol that achieves communication cost $O(\alpha+\alpha\log n)$. Thanks for your suggestion!

Line 124, $C=O(\alpha)$? Maybe something is missing there.

We have corrected the typo to be $C=O(\alpha)\cdot F_0(S)$, consistent with the implications of the statement -- thanks for pointing this out.

We thank the reviewer for their detailed feedback and insightful questions.

For the experiments...more data sets can be generated

We agree that increasing the number of datasets could provide additional empirical validation. Given the structure of the data, we anticipate that the overall pattern of results would remain similar. However, we see the value in this approach and will explore generating additional datasets to further strengthen our experimental evaluation

l 87 c 1: please define zipifan distribution

We have added the formal definition of Zipfian distribution in the preliminiaries and provided a forward pointer at this location.

l 124-129 c1: please provide an explanation for this behavior

We have corrected the typo to be $C=O(\alpha)\cdot F_0(S)$, consistent with the implications of the statement -- thanks for pointing this out!

l 237 c2: constant factor >> 4-approx

We have specified this in the algorithm.

l 670: what is P,Q?

$P$ and $Q$ are the two distributions $\mu_1$ and $\mu_2$ -- we have unified the notation now.

l 678: I think this formal description of the problem should be part of the main body

Thanks for the suggestion, we have moved this formal description to the main body in Section 2 and swapped out some of the full proofs to the appendix.

l 750: Here your arguments were to short for me to understand the proof as a non expert...please provide the precise arguments. (similar in l 770)

We have adjusted to language to clarify that the estimator provides an unbiased estimate to the total number of distinct elements and because of the number of samples, the variance is also sufficiently small. Then by applying a concentration inequality such as Chebyshev's inequality, it follows that the resulting estimator provides a $(1+\epsilon)$-approximation to the total number of distinct elements.

l 797L where does the factor 100 come from?

The number 100 comes from being a sufficiently large constant to apply the concentration inequalities that would result in a $(1+\epsilon)$-approximation. We have clarified this.

l 866: this seems natural; but please provide the padding argument here

We have added a description of the padding argument to the corresponding location in the appendix.

l 877: why ``Unfortunately''? I think this is a positive result

This is a positive result, but it rules out the proposed construction for a "hard distribution" toward the desired lower bounds, which is arguably unfortunate in the given context. We have rephrased this language.

l 974: please provide a reference for this lower bound

Thanks, we have added the reference to this lower bound, appearing in Jayram and Woodruff (2013).

appendix C.1 had some nice motivation; I think this should also be mentioned in the main body

Although there is insufficient room in the main body to include the entire motivation, we have added some of the motivation to the main body and included a pointer to Appendix C.1 for additional discussion.

Q1: You say that the new protocol is better if C is small. But this argument only takes the second summand into account. In your new bound the first summand is larger than the first summand in the old bound. Why is this first summand not important/dominated by the second?

Our first summand is $O(\alpha\log n\log\log n)$ while the first summand in the old bound is $O(\alpha\log n)$. Due to the small $O(\log\log n)$ factor, we did not optimize the first summand.

In fact, this discrepancy is due to Algorithm 1, which we included because it leads to a natural description of Algorithm 2 and 3. Instead, we can also reference an existing procedure so that our first summand becomes $O(\alpha\log n)$, without changing any other terms in our bound. Thus, we match the first summand of the old bound over all regimes. This was also picked up by Reviewer iXZ8, who pointed out the connection.

Q2: I don't understand why for non-binary vectors you want $v_i^{(a)}\ge 1$ and $v_i^{(b)}\ge 1$. For me, it seems more natural to require $v_i^{(a)}=v_i^{(b)}$. Does this make the problem significantly more complicated? Is this problem relevant in practice? Is this studied?

Intuitively, an item $i$ is shared across multiple servers $a$ and $b$ if $v_i^{(a)}\ge 1$ and $v_i^{(b)}\ge 1$. For the purposes of the distinct elements problem, there is no difference from the perspective of a server $a$ if $v_i^{(a)}=1$ or $v_i^{(a)}>1$ because either way, the server $a$ knows that $i$ has a non-zero count.

Q3: In most theorems you use completely different probabilities. Why is this the case? Is there an easy argument that any constant probability can be used? If yes, please provide such an argument.

Yes, any constant probability larger than $\frac{1}{2}$ can generally be used. This is because by taking $O\left(\log\frac{1}{\delta}\right)$ independent instances of an algorithm and computing the median, the probability of success is boosted to $1-\delta$.