On Fine-Grained Distinct Element Estimation
Authors: Ilias Diakonikolas
Daniel Kane
Jasper C.H. Lee
Thanasis Pittas
David Woodruff
Samson Zhou
Venue: ICML 2025 poster (2025)
Keywords: distinct elements
distributed model
communication complexity
data streams
Primary area: theory->everything_else

Abstract: We study the problem of distributed distinct element estimation, where $\alpha$ servers each receive a subset of a universe $[n]$ and aim to compute a $(1+\varepsilon)$-approximation to the number of distinct elements using minimal communication. While prior work establishes a worst-case bound of $\Theta\left(\alpha\log n+\frac{\alpha}{\varepsilon^2}\right)$ bits, these results rely on assumptions that may not hold in practice. We introduce a new parameterization based on the number $C = \frac{\beta}{\varepsilon^2}$ of pairwise collisions, i.e., instances where the same element appears on multiple servers, and design a protocol that uses only $O\left(\alpha\log n\log\log n+\frac{\sqrt{\beta}}{\varepsilon^2} \log n\right)$ bits, breaking previous lower bounds when $C$ is small. We further improve our algorithm under assumptions on the number of distinct elements or collisions and provide matching lower bounds in all regimes, establishing $C$ as a tight complexity measure for the problem. Finally, we consider streaming algorithms for distinct element estimation parameterized by the number of items with frequency larger than $1$. Overall, our results offer insight into why statistical problems with known hardness results can be efficiently solved in practice.

On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas' Daniel M. Kane² Jasper C.H. Lee Thanasis Pittas David P. Woodruff Samson Zhou²
Abstract
2003; Raskhodnikova et al., 2009; Kane et al., 2010; Cor-
mode et al., 2011; Woodruff & Zhang, 2012; 2014; Braver- man et al., 2018; Blasiok, 2020; Woodruff & Zhou, 2021; Ajtai et al., 2022; Blocki et al., 2023; Jain et al., 2023; Gribelyuk et al., 2024) due to both the simplicity of the question as well as its wide range of applications. We study the problem of distinct element estimation in a distributed setting, so that there are a servers that each receive a sub- set of the universe [n]] = {1, (l,...,.) n). The goal is for the servers execute protocol that can approximate the to- tal number of distinct elements, which is the number of coordinates j E [n]] that appears in at least some server. The protocol should use as small of an amount of total communication as possible, where the total communica- tion is the sum of the sizes of all messages exchanged in the protocol in the worst-case. To capture approximation, for prescribed accuracy parameter e 0, the goal is to output a (1 + --aaproxxiaation to the number of distinct elements. The problem of distinct element estimation across distributed dataset has a large number of applications, including database design (Finkelstein et al., 1988), data warehousing (Acharya et al., 1999; Gibbons, 2001), network traffic monitoring (Akella et al., 2003; Estan et al., 2003; Liu et al., 2020), internet mapping (Palmer et al., 2001). and online analytic processing (OLAP) (Shukla et al., 1996; Padmanabhan et al., 2003).
We study the problem of distributed distinet el- ement estimation, where a servers each receive subset of universe [n] and aim to compute a (1 + apprroxximtno to the number of distinct elements using minimal communication. While prior work establishes worst-case bound of @ (a log + - bits, these results rely on as- sumptions that may not hold in practice. We introduce a new parameterization based on the number C & of pairwise collisions, i.e., in- stances where the same element appears on multi- ple servers, and design protocol that uses only O (a log + // ş2 log ni bits, breaking previous lower bounds when C' is small. We further im- prove our algorithm under assumptions on the number of distinct elements collisions and pro- vide matching lower bounds in all regimes, es- tablishing C' as a tight complexity measure for the problem. Finally, we consider streaming algo- rithms for distinct element estimation parameter- ized by the number of items with frequency larger than 1. Overall, our results offer insight into why statistical problems with known hardness results can be efficiently solved in practice.
In the context of machine learning, distributed distinct ele- ment estimation plays a crucial role in many applications where data is distributed across multiple nodes or servers. For instance, in collaborative filtering (Resnick et al., 1994), such as recommendation systems (Aggarwal, 2016; Koren et al., 2009), estimating the distinct preferences or behav- iors of users across various platforms requires efficient dis- tributed algorithms. Similarly, in anomaly detection (Chan- dola et al., 2009), identifying rare or novel events across different data cources-such as network traffic or sensor data requires tracking unique occurrences without cen- tralized data aggregation. Distributed distinct element es- timation is also relevant in federated learning (McMahan et al., 2017), where machine learning models are trained across decentralized devices while keeping data local. Es- timating the number of distinet features or labels across distributed devices is essential for improving training effi- ciency. In large-scale graph analysis (Malewicz et al., 2010; Gonzalez et al., 2014), where nodes edges are distributed
1. Introduction
Estimating the number of distinct elements in a large dataset a fundamental question that was first introduced by Fla- jolet and Martin (Flajolet& & Martin, 1985) and has subse- quently received significant attention, e.g., (Cohen, 1997; Alon et al., 1999; Yossef et al., 2002; Durand & Flajolet,
'University of Wisconsin- Madison University of Califor- nia, San Diego UUiiersiity of California, Davis *Camegie Mellon University "Texas A&M University. Correspon- dence to: Ilias Diakonikolas <ilias @ cs. wisc.edu>, Daniel M. Kane <dakane @ @cs. les.uucs.edd. edu>> Jasper C.H.I Lee <jasper- wwe@uuddvvi.edue Thanasis Pittas <pittas @wisc.edu>, David P. Woodruff wanoodruffandrrww..mm www... Samson Zhou <sam- sonzhou gmm...com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

On Fine-Grained Distinct Element Estimation
across servers, this problem helps in tasks like counting distinet subgraphs community structures. Additionally, in streaming data applications (Manku & Motwani, 2002), such as real-time monitoring or natural language process- ing, estimating the diversity of items in large data streams is essential for efficient data summarization and decision- making.
Does the distributed distinct element estimation problem still require St (2 + ar log n) communii- cation across more "realistic" distributions?
1.1. Our Contributions
In this paper, we give resounding negative answer to the above question, translating to positive algorithmic results that break previous impossibility barriers. We introduce a novel parameterization of the distributed distinct element estimation problem, showing that although previous upper and lower bounds show optimality for the worst-case input, these hardness of approximation results do not necessar- ily apply across various regimes of our parameterization. Namely, we show that the complexity of the problem can be characterized by the number of pairwise collisions in the dataset. Formally, for vectors v(4), v(a) E (0, 13", we define the number of pairwise collisions be the num- ber of ordered triplets (a, b, i) such that 1 a < b o, E [m). and u. = 1g = 1. We remark that the as- sumption that the vectors (8() are binary is without loss of generality, as it turns out the resulting protocols and reductions will behave the same regardless of whether server has single instance or multiple instances of coor- dinate. Nevertheless for the sake of completeness, for vec- tors o')),..., e(a) E {0, ......m.......... mm", we define the number of pairwise collisions to be the number of ordered triplets
(Kane et al., 2010; Blasiok, 2020) gave a one-pass stream- ing algorithm for achieving (1 e)-aprroximation to the number of distinct elements on dataset from universe of size [nr]. using O ( + log r1) bits of space. This can be transformed into a distributed protocol across a servers that uses O ( + a lo bits of communication, since each server can locally simulate the streaming algorithm on their dataset and then pass the state of the algorithm to the next server. On the lower bound side, (Cormode et al., 2011) showed that distributed distinct element estima- tion requires (2aa) communication, while (Arackaparambil et al., 2009; Chakrabarti & Regev, 2012) showed a lower bound of Ω (+)). These lower bounds were then subse- quently strengthened by (Woodruff & Zhang, 2012) and finally (Woodruff & Zhang, 2014) for all parameter regimes to 2 (g= + log n. seemingly resolving the problem by showing that the protocol of (Kane et al., 2010; Blasiok, 2020) is optimal.
However, the lower bound instance of (Woodruff & Zhang, 2014) requires a constant fraction of coordinates to appear across a constant fraction of servers, which may be unreal- istic in many applications. For example, in traffic network monitoring, suppose each server oversees flow of commu- nication, corresponding to messages from individuals, so that the coordinates of the universe would correspond to IP addresses of the senders of the messages. Then the lower bound instance of (Woodruff& & Zhang, 2014) would require that a constant fraction of IP addresses send messages to a constant fraction of the servers, i.e., requires a constant fraction of all senders be high volume. In reality, previous studies have shown that internet traffic patterns (Adamic & Huberman, 2002) often follow a Zipfian distribution, i.e., polynomial decay law, c.f., Definition A.I.
(a, b, such that 1 S < b S a, i E [m]. and ef 2 1 and b.()) 2 1.
We first show a general protocol for the distributed distinct element estimation problem across general ranges of (S)).. the number of distinct elements in the dataset S that is the union of all items given to all servers.
Theorem 1.1. Given a dataset S on a universe of size with C = 0.0 (min (Fo(S), +)) pairwise collisions for parameter 3 2 1, distributed across a players, there exists a protocol that computes a (1 + e) eppproxxiinttinn to (o(
with probability least? 2 that uses
O (a n) + +0 +0mmin (Fo(8), ()) 2)) . VBlogn
More generally, it has long been observed that many large datasets across other domains follow a Zipfian distribu- tion. For example, the distribution of words in a natu- ral language (Zipf, 2013), e.g., user passwords (Wang & Wang, 2016; Wang et al., 2017; Blocki et al., 2018; Hou & Wang, 2023), the distribution of degrees in the internet graph (Kleinberg et al., 1999), and the distribution of pop- ulation sizes (Gabaix, 1999; Rhodes, 2023) have all been commonly observed to follow Zipfian distribution. Indeed, (Mitzenmacher, 2003) claims that "power law distributions now pervasive in computer science".. Thus it seems natural to ask
bits of communication.
Theorem 1.1 shows that the 2 (()) lower bound of
(Woodruff & Zhang, 2014) need not apply when the num- ber of pairwise collisions is in the range of o(a2 FS)). That is, the lower bound of (Woodruff & Zhang, 2014) only applies when there is constant fraction of coordinates that appear across a constant fraction of servers.
In the case where the number of pairwise collisions is less than the number of distinct elements, e.g., C < (S),,, we can further improve the guarantees of our protocol as follows:
2

---

On Fine-Grained Distinct Element Estimation
Theorem 1.2. Given a dataset S on a universe of size n with the promise that there are at most C S Fo(S) pair- wise collisions, distributed across a players, there exists protocol that uses total communication
Hence by Chebyshev's inequality, we have that with proba- bility at least 0.99, W 1 provides additive vj X error to (t) + +... + t,), conditioned on E. By Lemma 2.4, we have that Pr [8] 2 0.99. Thus by a union bound, with probability at least 0.98, Algorithm outputs a (1 + e)- approximation to Fo. Observe that conditioned on the event E, we have X I 0 (2)). Since the number of pairwise col- lisions is at most C', then F (S,) S X + C. Let Y denote the number of items from T sent across all players. Then we have E [X] S p(x + C). We have p min (1, 100G for 7j = 1u Note that then for Fo(S) = 52 (++), we have
y
Ô (a log + max Fo(S)) .²)
1
)
C logn)
bits, and with probability at least 3. outputs a (1 + 8)- approximation to Fo(S).
of x²x²
Theorem 1.2. Given a dataset S on a universe of size n with the promise that there are at most C S Fo(S) pair- wise collisions, distributed across a players, there exists a protocol that uses total communication
C
C²
BM S 0
22
52X²
Ô ( a (( log max (FO(S)
1 3. outputs a (1 + +)-
82)
)
) logn)
C
Since C S Fo(S) (X). then B|y] 0
C
Po(3)
Otherwise for Fo( = (+). we have E [Y] = O (C).
bits, and with probability at least approximation to Fo(S).
The desired claim then follows from Markov's inequality.
Proof. Consider Algorithm 2. Recall that with probabil- ity at least 0.99, (1 O Fo()) I Fo. 2' <
While ascertaining the number of pairwise collisions itself may be a difficult challenge and possibly lead to chicken- and-egg problem, remark that computing a loose upper bound C on the number of collisions can be performed much casier, particularly given distributional or other a priori side information about the number of collisions. For example, additional knowledge about the number of collisions can be collected using previous datasets from a similar source, in similar vein the auxiliary input that is often utilized by learning augheened algorithms (Mitzenmacher, 2018; Bal- can, 2020; Mitzenmacher & Vassilvitskii, 2020). We also remark that the number of pairwise collisions is an important statistic in other problems, such as uniformity testing (Di- akonikolas et al., 2018; Fischer et al., 2018; Acharya et al., 2019; Meir et al., 2019) and closeness testing (Diakonikolas et al., 2019).
(1+ (z) Thus it suffices to achieve a (1 + (e)) approximation to (S:). For each j E [m]. let Sq be the number of times) j appears in S,. Then we have
Fo.).) Fi (S.) m0 11 -...- min 1).
Let t, min min(0. - 1) for all j e [n]] be the excess mass
of j. so that
(S.).) Fi(S) - (41 +...+++... + (n).
Let & be the event that X is a 4-approximation to (o)). Since 7 = (((S) in the context of Algorithm 2 and X is a 4-approximation to SS, conditioned on E, then it suffices to achieve an additive 17. X = (e)- (S.) approximation to (t1 +... + tn) for 1) T
We remark that for the case when the number of servers for each item follows Zipfian distribution across the servers, then the total number of pairwise collisions is C = O (a) (o(S), provided that the Zipfian exponent is a constant larger than 1. On the other hand, the num- ber of distinct elements can be substantially larger than f. where is the desired accuracy for the output estimate for the number of distinct elements. Our results indicate that in this regime, only Ô (a log n) bits of communication suffice, which bypasses the known 2 (g+ + a log n) lower bounds. In particular, if the number of distinct elements is O (n) and ε is around 1 then the lower bounds indicate 2(()) v communication is necessary, which is substantially worse than our protocol that achieves Ô (a log communication.
Observe that the expected value of W. satisfies
p
E W.W.
1 - p_
1
Σ p. p- = 1-
+ In
SEin]
Moreover, we can upper bound the variance
V W.
Σ p (1))²
pl
5E[n]
Since p= = min (1,
100C -
and (tf + ... + ( S C, then
V W. 1 < x²
100C (2i +... + 2²)²² < x2x2
We complement Theorem 1.1 and Theorem 1.2 with a pair of lower bounds matching in B and :
p
100
3

---

On Fine-Grained Distinct Element Estimation
Theorem 1.3. Let B [1,aa]. Given a dataset S with C = =2(3- Fo(S)) pairwise collisions, distributed across a players, any protocol that computes (1 + s)- approximation to (S) with probability at least 2 3 uses
via simple reduction from previous work on non-promise set disjointness in the coordinator model (Braverman et al., 2013). Thus, the main contribution in Theorem 1.5 is to show that even the problem of approximating the number of duplicates requires a substantial amount of total communica- tion. We also give a simple protocol that uses O cce
vB 2 (min (Fo(S): )) communication.
Theorem 1.4. Given a dataset S with the promise that pairwise collisions
Ce
there are at most C' E [E- distributed across a players, any protocol that computes (1 + e) appppooximatiinn Fo(S) with probability at least 3 communication.
bits of communication, showing that Theorem 1.5 is near- optimal.
Further, we remark that given Theorem 1.2, a natural ques- tion would be to ask whether the promise of the upper bound on C' must be known in advance in order to achieve im- proved communication bounds, perhaps through a prelim- inary subroutine to estimate C. However, Theorem 1.5 shows that in general, one cannot estimate C' uusinn "small" total communication when C' is small.
uses 9
FOSTT
We remark that Theorem 1.3 follows immediately as a pa- rameterization of a lower bound from (Woodruff & Zhang, 2014), while Theorem 1.4 is perhaps our most technically involved contribution. We recall that well-known results, e.g.. (Cormode et al., 2011) 1) additionally show that regard- less of the number of pairwise collisions and regardless of (S), any protocol that estimates (S) to constant factor requires Oax communication. Thus, Theorem 1.3 and Theorem 1.4 together imply the lower bound results in Table 1.
Finally, we complement our theoretical results with a num- ber of empirical evaluations in Scction 3. We show that the standard CAIDA dataset, often used to analyze statistics on virtual traffic networks, is surprisingly skewed, allowing our algorithm to outperform the previous worst-case theoretical bounds by several orders of magnitude. While this may be an extreme case, it demonstrates that our algorithm can achieve significantly better performance in practice, align- ing with our theoretical guarantees and serving as a proof- of of-concept that illustrates the accuracy-vs- comommmiccmnm tradeoffs in real-world scenarios.
Moreover, we remark that for the regime where C s (S), then (S( = Eieta] || becomes an additive 8. (S) approximation to Fo(S), and so the players can use O (a log n) bits of communication deterministically compute a (1 E) mulltiplicative approximation to (S)).
Our results can be viewed as a first step toward analyz- ing standard statistical problems with known lower bounds, e.g.. (Woodruff& & Zhang, 2012; 2014) through the lens of parameterized complexity. Thus our work makes important progress toward a better understanding of natural parame- ters that explain why these problems are not challenging in practice. We summarize results for the distributed distinct elements estimation problem in Table 1.
Paper organization. The remainder of this paper is struc- tured as follows. In Section 2.1, we present a parameterized lower bounds for the distributed distinct element estimation problem, assuming the communication complexity of the so-called GapSet problem. We then show correspond- ing upper bound in Section 2.2. We defer the proof of the GapSet problem to Appendix B and Appendix C. We provide our experimental results in Section 3. Finally, we show in Appendix D that both distinct element estimation and norm estimation can similarly be parameterized in the streaming model. To discussion of the notation as well as relevant background statements, we refer the reader to Appendix A.
In proving Theorem 1.4, we first show the hardness of ap- proximation for the closely related distributed duplication detection problem, in which the goal is for the a servers to approximate the total number of duplicates, where a dupli- cate is defined to be coordinate j E [n] that appears on at least two distinct servers. For discussion on the applica- tions of the distributed duplication detection problem, see Appendix C.
2. Distributed Distinct Element Estimation
Theorem 1.5. Let C. be an input parameter for the number of duplicates and e E (0, 1) be an accuracy parameter. Suppose there are a players, each receiving a set of at most items from a universe of size N ((s). Then any protocol II that with probability at least 23. identifies whether there are fewer than (1 - E) C duplicates or more than (1 + E). C duplicates requires M(as) communication g2-
In this section, we study the problem of Fo approximation. In Section 2.1, we prove Theorem 1.3, showing that the communication complexity for the distributed distinct el- ement estimation problem is function of the number of pairwise collisions distributed across the players. In Sec- tion 2.2, we give an algorithm for the distributed distinct element estimation problem that uses total communication which is function of the number of pairwise collisions, i.c., the algorithm corresponding to Theorem 1.2.
for C < z2 and 2
as communication for C Z 4
C82)
We remark that for & = O, the lower bound of (2sss) follows
4

---

On Fine-Grained Distinct Element Estimation
C - 3 Fo(S),
Fo(5) < 2/
Fo(5) 2
pz
Theorem 1.1
O logo n + v3. (F()) logn)
0
a log n +
188
log
Theorem 1.3
Di(a + (F())
Ω2 a+
E²
C= = F.()) < C, 8. Fo(S)
Fo(S) <
Po(S) 2 2z
Theorem 1.2
O a logg n + logn
O (a + 3 logn)
Theorem 1.4
Ω a + g2
3.
Table A summary of our results for the distributed distinct elements estimation problem on a universe of size n across a servers, parameterized by the number C' of collisions across the a servers, and the accuracy parameter E (0, 1).
Distinct elements estimation. We now formally define the distributed distinct element estimation problem in the coordinator model of communication, which was intro- duced by (Dolev & Feder, 1992). There exist a servers with vectors p((), ".,,,,,,,,,,, vfa) E (0.1)* on a universe of size [n]. The vectors define an underlying frequency vector bb()) We interchangeably refer to the servers either players or parties, including specific server that is designated the coordinator for the protocol. Each of the servers have access to private sources of randomness. There is private channel between every server and the coordi- nator, but there are no channels between the other players, so all communication must be performed through the co- ordinator. We assume without loss of generality that the protocol is sequential and round-based, i.c., in each round the coordinator speaks to some number of players and await their responses before initiating the next round. Therefore, the protocol must be self-delimiting so that all parties must know when each message has been completely sent.
problem called SUM DISJ, in which there a players Pt. Pl.... Pa with inputs X1.... Xx E {0, 1 and coor- dinator C and Y E f0, 13th The vectors ,,...., Xa. Y are organized into blocks x( yú) for i E [a] and [t]. each with L coordinates. The inputs to each block of X, and Y are randomly generated instances of two-player set disjointness, i.c., there are instances of set disjointness, each with universe size L, generated as follows. For each E [L] one of the following events occurs:
With probability 1. is given to X1.
With probability 1. is given to Y.
With probability 1. is not given to either X₃ or Y.
After this process is performed for each i E [L]. special coordinate e E [4] is then chosen uniformly at random and the allocations of e are reset, so that initially, c is not given to either X, or Y. Then, one the following events occurs:
Given an accuracy parameter E, the goal is to perform a protocol II so that the coordinator outputs a (1 + E)- approximation to (v) after the protocol has completed. The communication cost of the protocol II is the total num- ber of bits sent by all parties in the worst-case output. Thus, we remark that up to constants, we obtain the same results for the message-passing model, where servers are allowed to communicate directly with each other.
With probability
2. c is given to both players.
With probability 2. e given to neither player.
The inputs X2...., are then similarly generated, but conditioned on the value of Y, so that each pair (X,,Y) forms an input two-player set disjoint- ness. Let DISJ(X!"), y(i) = 0 if the special coor- dinate is given to neither player, i.e., the instance is disjoint, and let DISJ(X!"), yúl) 1 otherwise. We then define SUM - Di., E Ee= DISJ(X()) y())
For both our algorithms and lower bounds, the assumption that each local vector is binary is without loss of generality, because the resulting protocols and reductions will behave the same regardless of whether server has a single instance or multiple instances of a coordinate.
to be
(Woodruff & Zhang, 2014) proved that computing ad- ditive O (Vat) error to SUM DISJ(XXI,........ X., Y) re- quires ((atT.) communication. They then reduced the prob- lem of Fo approximation from SUM - DISJ as follows.
2.1. Lower Bounds for Distributed Distinct Element Estimation
To show Theorem 1.3, our starting point is the lower bound instance of (Woodruff & Zhang, 2014), which first defines a
Given an instance K,,...,Kay of SUM - DISJ, the co- ordinator creates the indicator vector Z corresponding to
5

---

On Fine-Grained Distinct Element Estimation
[1L]] \ Y. Observe that for 0 (+ta) and IL O (+) a (1 + >aapproximation to (X + ................................ + Xa + 7) suffices for the coordinator to compute an additive 0 (Vat) error
(1 + -aappooximaaooon to Fo( is an additive e (o approximation to (S). Consider the hard instance of The- orem 1.5 and recall that it places the C' pairwise collisions across unique coordinates, so that Fo(S) = Fi(S) C. Thus an additive e Fo((S) approximation to Fo(S) is an additive s- FF) approximation to C, which is also mul-
to SUM - DIS Y), given Y.
Crucially, a constant fraction of the items are given to a constant fraction of the players, with constant probability due to the distribution of set disjointness, where each coor- dinate given to each player X; with probability at least 4- Therefore, 5 ( (22) coordinates in the frequency vector Xi +..... + X. + Z have frequency A(x), with probability at least 0.99. Thus we have the following:
tiplicative (1 F=(()) -pproximation to C. Observe that
the a players can use O (log 2) = 0 (C)) bits of communi- cation to compute Fi (S) exactly. By Theorem 1.5, multi-
plicative (1 s-Fo(S) -aproximation C' approximation
requires ?
communication.
Lemma 2.1. (Woodruff & Zhang, 2014) Given a dataset S with (S) 2 (2²) and C S2(a² Fo())) pairwise collisions, distributed across a players, any protocol that computes a -aprroxiaattitaoooonn to FS(S) with probability at least Th4 uses Q (o) communication.
Fo
2.2. Upper Bounds for Distributed Distinet Element Estimation
In this section, present upper bounds for the distributed distinct element estimation problem. In particular, we de- scribe our algorithm that guarantees Theorem 1.2, which shows that the communication complexity of the problem is paraemterized by the number of pairwise collisions. We first recall the following guarantees for a constant-factor approximation to (S)).
In fact, for 3 < o, we can embed the same problem across 3 players to obtain the following:
Corollary 2.2. Let 3 [1,a²]. Given a dataset S with (o) = (2)) and C = ())))F(s) pairwise collisions, distributed across players, any protocol thut computes (1 + 5) -approximation to Fo(S) with probability at least ahe communication.
uses 92
VB
Theorem 2.4. (Kane et al., 2010; Blasiok, 2020) There exists an algorithm that outputs 4-approximation to the number of distinct elements and uses O (a log bits of communication.
Similarly, for Fo(s) = =0 (z)) with Fo(s) = M(a), it fol-
lows that for t- 0 Fo(s) a
and tL= ((Fo(s)), (1 s)-
Now, prove Theorem 1.1 through Algorithm 1.
approximation to FX +... + Xa + 2) suffices for the coordinator to determine SUM - DISJ( X.,, Y) up to additive error O (Vat), given Hence, we have:
Algorithm (1 + approxxmmttio to Fo
Input:
Items given to a players from a universe of size [n]]
Corollary 2.3. Let 8 [1, a²). Given a dataset S with Fo(s) = (+) and C 2(3 Fo(s)) pairwise colli- sions, distributed across a players, any protocol that com- putes a (1 + E) to Fo(S) with probability at least 3 uses a (VB (o) communication.
accuracy parameter E E (0, 1)
Output: (1 + approxxiimtioo to the number of distinct
items
1: Let X be 4-approximation to Fo
Lemma 2.4
2: Let io be the largest integer such that
1000
Putting together Corollary 2.2 and Corollary 2.3, we have:
3: x <- max(0, in)
Theorem 1.3. Let B E [1,a²]. Given dataset S with C = 223 (S)) puirwise collisions, distributed across a players, any protocol that computes (1 + +)- approximation to Fo) with probability at least 2 vB. 2 (iin (Fo(S), ) communication.
4: Let T, be subset of [r]] where each item is subsampled with probability 1
Each player sends their items in Tj
3 uses
6: Let 7 be the number of unique sent items
7: Return 2
We now give the proof of Theorem 1.4, assuming the cor- rectness of Theorem 1.5, which we defer to Section C.
We now show the parameterized complexity of the dis- tributed distinct elements estimation problem.
Theorem 1.4. Given a datasel S with the promise that there are at most C E [e- Fo(S), Fo(S) pairwise collisions distributed across a players, any protocol that computes a (1 + approoxiiatoo to Fo(S) with probability at least 2
Theorem 1.1. Given a dataset S on a universe of size n with 8-0 (min (Fu(S), 22)) pairwise collisions for a parameter 3 2 distributed across a players, there exists protocol that computes a (1 + approxxmmatii to Fo(S) with probability at least 2 3 that uses
uses Ω
communication.
O (a n) + (min (Fo(S), -20)),,))) )) . VBlogn
Proof. Suppose a = (1). Note that a multiplicative
6

---

On Fine-Grained Distinct Element Estimation
bits of communication.
Algorithm 2 (1 + approxximaiio to Fo. given an upper
bound the number of collisions
Proof. Consider Algorithm 1. Let Fo(S) be the num- ber of distinct items across all players. Note that we have E Z 2 = Fo) and V Z 2 FS( 2' I (e (8)), Hence conditioned on the correctness of X, by Chebyshev's inequality, we have that with probability at least 0.99.
Input:
Items given to a players from a universe of size [n]. accuracy parameter E E (0, 1), upper bound C on the number of pair-wise collisions
Output: (1 + aaprroxiattiiiiinnnnn the number of distinct
250
items
I: Let X be 4-approximation to Fo
DLemma 2.4
2: Let io be the largest integer such that
X 2 E
1000
3: i < min(0, io)
(1-6)- S Z.2 S (1) Fo(S).
4: Let S; be subset of [rx] where each item is subsampled with probability 전
It remains to show that the total communication used by the protocol is O (a log n) + O (min (F)()), =))= vB log bits. Conditioned on the correctness of X, we have by the g". Hence by Markov's in-
Assume without loss of generality each player has a
binary vector e()) E {0, 13"
6: Each player sends their total number of items in S
definition of that E [2] < 800
7: Let 2 be the sum of these numbers
equality, we have that Z s
10 with probability at least
8: + fo f- min (1, 100C
0.99. Let & be the event that Z I min 1000 Fo(S))
Let be a subset of S; where each item subsampled with probability p
10th ee; Fo())) and for i E [N], let H; be
Let N = min the number of players with item i, that 0 S H, I a. Then conditioned on E. the number of pairwise collisions
10: Each player sends their items in T
11: Let W = =Ejer max (0, 1y- where v = EiE(a) vi()
be the excess mass in T
2 11 - 7. so that C 2 # H12 N. By the Root-Mean Square- Arithmetic Mean Inequality, we have that if there are C' c 3. 0 (min (Fo(S), +)) pairwise collisions, then
is C
(1)) .... + (MN). Note that (0)
12: Return - W
Proof. Consider Algorithm 2. Recall that with probabil- ity at least 0.99, (1 O (o)) < Fo(S.) 2 < (1+ Thus it suffices to achieve a (1 + O (s)) approximation to (5.).. For each j E [n], let fy be the number of times j appears in S.. Then we have
= 0 -0 (VBN)
H1 + + HN =
1 = min (Fo(S), 3/4 )) VB.
Po(S.) Fi (S.) - min(0, fi 1))- -...- 000.0.mmi(0...... f, 1).
Thus the a players have at most O (min (Fo(S), ))) vB items in S, from universe of size [n]. so the communication for sending these items is O (a log n) O (min (S), )) /3llgg bits. Finally, recall from Lemma 2.4 that O lo bits of communication suf- fices to compute a fanstont-factor approximation to Fo(S). Thus, the total communication is at most O (a log n) + O (min (S)( ))) /Bllg n bits.
Lett, ty min f, 1) for all j [m] be the excess mass of j. so that
Fo(S.) = = - (41 +... ...... (.))
Let & be the event that X a 4-approximation to (S.). Since Z Fi (S.) in the context of Algorithm and X is a 4-approximation to (S,)) conditioned on E, then suffices to achieve an additive 1) X O (E) Fu approximation +..+ to (41 +... lm)) for 1 = 5
The guarantees of Theorem 1.2 then follow from Algo- rithm2 2:
Theorem 1.2. Given dataset S universe of size n
Observe that the expected value of W 1 satisfies
p
with the promise that there are at most C S Fo(S) pair- wise collisions, distributed across a players, there exists a protocol that uses total communication
1 -1---
E
W. P
Σ p- -1 bn
P
JE(m)
δ ( aa logg + max (O(S) x2 - logn
C
Moreover, we can upper bound the variance
bits, and with probability at least 3. outputs a (1 + E)- approximation to (S(S).
W
W
<
1
Σ p (1
P
p2
JE
mg
7

---

On Fine-Grained Distinct Element Estimation
Since p= = min (L.
100C xpx² and (ff ff.....+ + ( S C, then
with the most activity and computed the number of inter- actions per sender that IP address, plotring the resulting distribution in Figure lb.
1 W.
n x²
100C (e +..... 20²² 7 xx²
P_
100
We then evaluate our distributed protocol in Algorithm 1. In particular, we consider the total communication of our algorithm compared to the total communication given by the analysis of the standard protocol, which sends a sketch of size O (+) ) for each of the a servers. Correspondingly, we set our algorithm to also have accuracy O (c) and compare the communication, across various values of 2F with p E {2,3, 4,5,6, 5, 7, 8, 9, 10, 11}. These results appear in Figure 2a. Finally, we studied the accuracy of our distributed protocol. We evaluated the output of our algorithm for = 2F across p E 1, 1, 4,5} and computed the error with respect the true number of unique sender IP addresses, which totaled 42200. We give these results in Figure 2b.
Hence by Chebyshev's s inequality, we have that with proba- bility at least 0.99, W provides an additive 1) X error to (t1 +... + t.). conditioned on E. By Lemma 2.4, we have that Pr 2 0.99. Thus by a union bound, with probability at least 0.98, Algorithm 2 outputs a (1 + E)- approximation to Fo. Observe that conditioned on the event E. we have X S O lisions is at most C, then (S.))) S X C. Let Y denote the number of items from T sent across all players. Then we have E [X] S p(X + C). We have p- = min 11, 100C x
((+) 4))
Since the number of pairwise col-
for 17 = 5 10. Note that then for Fo( = Ω ( (,),, we have
BM 0 0 (
C
C2
x2x
+
x2X2
Our empirical evaluations were performed with Python 3.11.5 on a 64-bit operating system on an Intel(R) CTM) i7-3770 CPU, with 16GB RAM and 4 cores with base clock 3.4GHz. The code is publicly available at https: / //github. com/ stc//samsss samsonzhou//DKLPWW
Since C S Fo()) 0 (X), then
E B = 6² Fo(5)
Otherwise for (o( 0 (+)), we have E Y 0 (C)-
Results and discussion. As virtual traffic is generally known to be dominated by few heavy-hitters, it was not altogether surprising that the distributions of activity for both receiver IP addresses and sender IP addresses were skewed. However, it was a bit surprising that when fit to a Zipfian power law so that the frequency of the i-th most common interaction is roughly C. the receiver IP address distribution returned roughly s z 0.743 and C' z 1404.68, which indicated a highly skewed distribution. By comparison, the activity distribution returned more modest R 0.344 and C ~ 43.93. Indeed, we emphasize that although both graphs in Figure appear linear, the scale for the receiver distribution is actually logarithmic.
The desired claim then follows from Markov's inequality. 0
3. Empirical Evaluations
In this section, we describe our empirical evaluations for evaluating our distributed protocol for distinet element esti- mation. We used the CAIDA dataset (CAIDA, 2016), which consists of anonymized passive traffic traces collected from the high-speed monitor at the "equinix-nye" data center. This dataset is widely used for statistical analyses for traffic network monitoring. in particular empirical analyses of algo- rithms for distinct element estimation, norm and frequency moments, and heavy-hitters (Hsu et al., 2019; Chen al., 2022; Lin et al., 2022; Ivkin al., 2022). From 12 minutes of internet flow data totaling approximately 40 million total events, we extracted the first 1 million events, each repre- senting an interaction between a sender IP address and a receiver IP address.
Because the distribution so skewed, the number of pair- wise collisions is quite small, as most of the receiver IP addresses only receive small amount of activity. There- fore, our protocol vastly outperforms the theoretical bounds for the standard benchmark by several orders of magnitude, as evident in Figure 2a. Moreover, our algorithm quickly converges to the optimal solution as e decreases, achiev- ing 70% error for ε = 1, quickly up to more than 95% 1 in Figure 2b. This matches our theoreti- error for E = 16 cal guarantees, thus serving as simple proof-of-concept demonstrating the accurcy-vs-commmuiccl tradeoffs.
Experimental setup. We estimate the total number of distinct sender IP addresses. As the events are partitioned across different receiver IP addresses, each receiver holds different set of users from the total collection of active sender IP addresses. To show our setting is valid for our theoretical assumptions, we considered two different distri- butions. First, we computed the number of unique senders per receiver and plotted a logarithmic scale of the result- ing distribution in Figure 1a, We then isolated the receiver
4. Conclusion
In conclusion, this paper addresses the distributed distinct element estimation problem, where previous results indi-
8

---

On Fine-Grained Distinct Element Estimation
Histogram of Senders per Receiver
Histogram of Interactions on Active Receiver
400
Number of feceiverr
10F
200
107
200
100
10F
10P
304
102
10a
10a
16a
of Unique Senders
Interactions
(a) Histogram of Receivers
(b) Histogram of Activity
Figure I: Histogram of unique senders per receiver in Figure 1a. Histogram of activity per sender most active receiver Figure lb.
Probab liy vs. Samples
Probability vs. Error
10
1,00
0.mh
093
20h
6.40
6.85
0.80
307
107
15
(a) Communication vs. Sampling Probability
(b) Sampling Prohability vs. Accuracy
cate that ④ (a logn + .) bits of communication both necessary and sufficient in the worst case. However, the assumption of large input sizes across many servers be unrealistic in practical scenarios. To address this, we introduce a new parameterization based on the number C of pairwise collisions distributed across the a players. Our al- gorithm, which uses O (a log n log log n + vC logn) bits of communication, demonstrates that small values of C can break existing lower bounds. We also establish matching lower bounds for all regimes of C, showing that provides a tight characterization of the communication complexity for this problem. Ultimately, our work offers new insights into why standard statistical problems, despite known im- possibility results, be efficiently tackled in real-world scenarios.
Acknowledgments
Ilass Diakonikolas is supported by NSF Medium Award CCF-2107079 and H.I. Romnes Faculty Fellowship. The work of Jasper C.H. Lee done in part while he was at UW Madison, supported by NSF Medium Award CCR- 2107079. Thanasis Pittas is supported by NSF Medium Award CCF-2107079. Daniel Kane is supported by by NSF Medium Award CCF-2107547 and NSF CAREER Award CCF-1553288. David Woodruff is supported in part by Office of Naval Research award number N000 1221 12647 and a Simons Investigator Award. The work was conducted in part while David P. Woodruff and Samson Zhou were visiting the Simons Institute for the Theory of Computing as part of the Sublinear Algorithms program. Samson Zhou is supported in part by NSF CCF-2335411.

---

On Fine-Grained Distinct Element Estimation
Impact Statement
Bar- Mas-Yossef, Z.., Jayram, T. S., Kumar, R., Sivakumar, D., and Trevisan, L. Counting distinct elements in data stream. In Randomization and Approximation Techniques, 6th International Workshop, RANDOM, Proceedings, pP.
This paper presents work whose goal is to advance the the- oretical foundations of distributed computing. There are many potential socictal consequences of our work, none which we feel must be specifically highlighted here.
1-10, 2002. 1, 15
Bar- Yossef, Z., Jayram, T. S., Kumar, R., and Sivakumar, D. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci., 68(4): 702-732, 2004. 14, 15, 17, 18, 20, 21
References
Acharya, J., Canonne, C. L.,, and Tyagi, H. Communication- constrained inference and the role of shared randomness. In Proceedings of the 36th International Conference on Machine Learning, ICML, USA, pp. 30-39, 2019. 3
Bilenko, M. and Mooney, R. J. Adaptive duplicate detection using learnable string similarity measures. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 39-48, 2003. 25
Acharya, S., Gibbons, P. B.. Poosala, V., and Ramaswamy, S. The aqua approximate query answering system. In SIG- MOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data, pp. 574-576, 1999.
Bitton, D. and DeWitt, J. Duplicate record elimination in large data files. ACM Trans. Database Syst., 8(2): 255-265, 1983. 25
Adamic, I.. A. and Huberman, B. A. Zipf's law and the internet. Glottometrics, 3(1):143-150, 2002. 2
Blasiok, J. Optimal streaming and tracking distinct elements with high probability. ACM Trans. Algorithms, 16(1):3:1
Aggarwal, C. C. Recommender Systems- The Textbook. Springer, 2016.
3:28, 2020. 1, 2, 6, 15
Blocki, J., Harsha, B., and Zhou, S. On the economics of offline password cracking. In 2018 IEEE Symposium on Security and Privacy, SP, Proceedings, pp. 853-871, 2018. 2
Ajtai, M., Braverman, V., Jayram, S., Silwal, S., Sun, A. Woodruff, D. P., and Zhou, S. The white-box adver- sarial data stream model. In PODS '22: International Conference on Management of Data, pp. 15-27, 2022.
Blocki, J., Grigorescu, E., Mukherjee, T., and Zhou, S. How to make your approximation algorithm private: A black-box differentially-prine able approximation algorithms of functions with low sen- sitivity. In Approximation, Randomization, and Combi- natorial Optimization. Algorithms and Techniques, AP- PROX/RANDOM, pp. 59:1559:199 159:24,, 2023.
Akella, A., Bharambe, A., Reiter, M., and Seshan, S. De- tecting ddos attacks on isp networks. In Proceedings of the Workshop on Management and Processing of Data Streams, pp. 1-2, 2003.
transformation for tun-
Alon, N., Matias, Y., and Szegedy, M. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci., 58(1):137-147, 1999.
Bloom, B. H. Space/time trade-offs in hash coding with allowable errors. Commun. ACM, 13(7):422-44) 1970. 25
Ananthakrishna, R., Chaudhuri, S., and Ganti, V. Eliminat- ing fuzzy duplicates data warehouses. In Proceedings of 28th International Conference on Very Large Data Bases, VLDB, pp. 586-597, 2002. 25
Braverman, M., Ellen, F., Oshman, R., Pitassi, T., and Vaikuntanathan, V. A tight bound for set disjointness in the message-passing model. In 54th Annual IEEE Sym- posium on Foundations of Computer Science, FOCS, pp. 668-677. IEEE Computer Society, 2013. 4, 17
Anupam, V., Mayer, A. J., Nissim, K., Pinkas, B., and Reiter, M. K. On the security of pay-per-click and other web advertising schemes. Comput. Networks, 31(11-16): 1091-1100, 1999. 25
Braverman, M., Garg. A., Pankratov, D.,, and Weinstein, O. Information lower bounds via self- reducbiddci Theory Comput. Syst. 59(2):377-39,, 2016. 18, 20
Arackaparambil, C., Brody, J., and Chakrabarti, A. Func- tional monitoring without monotonicity. In Automata, Languages and Programming, 36th International Collo- quium, ICALP, Proceedings. Part I, pp. 106, 2009.
Braverman, V., Grigorescu, E.,, Lang, H., Woodruff, D. P., and Zhou, S. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Random- ization, and Combinatorial Optimization. Algorithmms and Techiqqus,APPPROX/AAAI APPROX/RANDOM, pp. 7:1-7:22, 2018. 1,
Balcan, M. Data-driven algorithm design. In Roughgarden, T. (ed.), Beyond the Worst-Car Analysis of Algorithmss pp. 626-645. Cambridge University Press, 2020.
10

---

On Fine-Grained Distinct Element Estimation
CAIDA.
Diakonikolas, I., Kane, D. M., and Stewart, A. Sharp bounds The caida uesd anonymized internet traces. https: http://wwwwccccooo caida org/ /aataaalaal log/ datasets/ https/ppasssveeseeeeeeeeeeeeeeee 2016. 8
for generalized uniformity testing. In Advances in Neu- ral Information Processing Systems 31: Annual Confer- ence on Neural Information Processing Systems 2018, NeurlPS, pp. 6214-6213, 2018.
Chakrabarti, A. and Regev, O. An optimal lower bound on the communication complexity of sap-hamming-distaan SIAM J. Comput., (((5):1299-133)) 2012. 2, 18, 34
Diakonikolas, I., Gouleakis, T., Peebles, J., and Price, E. Collision-based testers are optimal for uniformity and closeness. Chic. J. Theor. Comput. Sci., 2019. 3
Chakrabarti, A., Khot, S., and Sun, X. Near-optimal lower bounds on the multi-party communication complexity of disjointness. In 18th Annual IEEE Conference Computational Complexity (Complexity), pp. 107-117, 2003. 17, 20
Dolev, D. and Feder, T. Determinism vs. nondeterminism in multiparty communication complexity. SIAM J. Comput., (1(5)889-8955 1992. 5
Durand, M. and Flajolet, Loglog counting of large cardi- nalities (extended abstract). In Algorithms ESA 2003, 11th Anmual European Symposium, Proceedings, pp. 605- 617, 2003.
Chakrabarti, A., Kondapally, R., and Wang, Z. Information complexity versus corruption and applications to orthogo- nality and gap-hamming. In Approximation, Randomiza- tion, and Combinatorial Optimization. Algorithms and Techniques- 15th International Workshop, APPROX, and 16th International Workshop, RANDOM. Proceedings, pp. 483 494, 2012. 20
Estan, C., Varghese, G., and Fisk, M. Bitmap algorithms for counting active flows high speed links. In Proceed- ings of the 3rd ACM SIGCOMM conference Internet measurement, pp. 153-166, 2003.
Chandola, V., Banerjee, A., and Kumar, V. Anomaly detec- tion: A survey. ACM Comput. Surv., 11:3::15: 2009.
Fellegi, I. P. and Sunter, A. B. A theory for record linkage. Journal of the American Statistical Association, 64(328): 1 1183-1210, 1969. 25
Charikar, M., Chen, K., and Farach-Colton M. Finding frequent items in data streams. International Collo- quium Automata, Languages, and Programming, pp. 693-703. Springer, 2002. 19,30
Finkelstein, S. J., Schkolnick, M., and Tiberio, P. Physical database design for relational databases. ACM Trans. Database Syst., 13(1):91-128, 1988.
Chaudhuri, S.. Ganti, V., and Motwani, R. Robust identi- fication of fuzzy duplicates. In Proceedings of the 21st International Conference on Data Engineering, ICDE, pp. 865 876, 2005. 25
Fischer, O., Meir, U., and Oshman, R. Distributed unifor- mity testing. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC, pp. 455- 464, 2018.
Flajolet, P. and Martin, G. N. Probabilistic counting algo- rithms for data base applications. J. Comput. Syst. Sci., 31(2):182-209 1985.
Chen, Y., Indyk, P., and Wagner, T. Streaming algorithms for support-aware histograms. In International Confer- on Machine Learning, ICML, pp. 3184-3203, 2022.
Gabaix, X. Zipf's law for cities: an explanation. The Quarterly journal of economics, 114(3):739 1999. 2
Cohen, E. Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci., 55(3):441-453 1997.
Gibbons, P. B. Distinct sampling for highly-accurate an- swers to distinet values queries and event reports. In VLDB, Proceedings of 27th International Conference Very Large Data Bases, pp. 541-550, 2001.
Cohen, W. W. and Richman, J. Learning to match and cluster large high-dimensional data sets for data integration. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 475 480, 2002. 25
Gonzalez, J. E., Xin, R. S., Dave, A., Crankshaw, D., Franklin, M. J., and Stoica, I. Graphx: Graph processing in distributed dataflow framework. In 11th USENIX Symposium on Operating Systems Design and Implemen- tation, OSDI, pp. 599-699999999 613. USENIX Association, 2014.
Cormode, G., Muthukrishnan, S., and Yi, K. Algorithms for distributed functional monitoring. ACM Trans. Algo- rithms, 7(2):21:1-21: 2011. 2,

---

On Fine-Grained Distinct Element Estimation
Gopalan, and Radhakrishnan, J. Finding duplicates in data stream. In Mathieu, C. (ed.), Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algoritums, SODA, pp. 402-411, 2009. 25
Symposium on Principles of Database Systems, PODS, pp. 41-52, 2010. 1, 6, 15
Kilss, B. and Alvey, W. Record Linkage Techniques, 1985: Proceedings of the Workshop on Exact Matching Method- ologies, volume 1299. Department of the Treasury, In- ternal Revenue Service, Statistics of Income 1986. 25
Gribelyuk, E., Lin, H., Woodruff, D. P., Yu, H., and Zhou, S. A strong separation for adversarially robust lo estimation for linear sketches. In 65th IEEE Annual Symposium Foundations of Computer Science, FOCS, pp. -2343, 2024.
Kleinberg, J. M., Kumar, R., Raghavan, P., Rajagopalan, S., and Tomkins, A. The web as a graph: Measurements, models, and methods. Computing and Combinatorics, 5th Annual International Conference, COCOON, Pro-
Håstad, J. and Wigderson, A. The randomized communica- tion complexity of set disjointness. Theory Comput.. 3 (1):211-219, 2007. 17
ceedings, pp. 1-17, 1999. 2
Hernández, M. A. and Stolfo, S. Real-world data is dirty: Data cleansing and the merge/purge problem. Data mining and knowledge discovery, 2:9-37, 1998. 25
Koren, Y., Bell, M., and Volinsky, C. Matrix factorization techniques for recommender systems. Computer, 42(8):
30-37, 2009. 1
Lin, H., Luo, T., and Woodruff, D. P. Learning augmented binary search trees. In International Conference on Ma- chine Learning ICML, pp. 13431-13446 2022. 8
Hou, Z. and Wang, D. New observations on zipf's law in passwords. IEEE Trans. Inf. Forensics Secur. 18:517- 532, 2023. 2
Liu, 7., Zhou, S., Rottenstreichh O., Braverman, V., and Rexford, J. Memory-efficient performance monitoring on programmable switches with lean algorithms. In 1st Sym- posium on Algorithmic Principles of Computer Systems. APOCS, pp. 31 31-44, 2020.
Hsu, C., Indyk, P., Katabi, D., and Vakilian, A. Learning- based frequency estimation algorithms. In 7th Interna- tional Conference on Learning Representations, ICLR. OpenReview.net, 2019.
Indyk, P. and Woodruff, D. P. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pp. 202-208, 2005. 18
Malewicz, G., Austern, M. H.,, Bik, A. J. C., Dehnert, J. C.,, Horn, I., Leiser, N., and Czajkowski, G. Pregel: a system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD, pp- 135-146, 2010.
Ivkin, N., Liberty, E., Lang, K. J.. Karnin, Z. S., and Braver- man, V. Streaming quantiles algorithms with small space and update time. Sensors, 22(24);9612, 2022.
Manku, G. S. and Motwani, R. Approximate frequency counts over data streams. In Proceedings of 28th Interna- tional Conference on Very Large Data Bases, VLDB, pp. 346-357, 2002. 2
Jain, P., Kalemaj. I., Raskhodnikova, S., Sivakumar, S., and Smith, A. D. Counting distinct elements in the tursstile model with differential privacy under continual obser- vation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023. NeurlPS, 2023.
McMahan, B., Moore, E., Ramage, D., Hampson, S., and y Arcas, B. A. Communication efficiien learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS, pp. 1273-1282, 2017.
Jayram, T. S. and Woodruff, D. P. Optimal bounds for johnson-linde lindenstrauss transforms and streaming problems with subconstant error. ACM Trans. Algorithms, 9()): 26:1 16:1-26:17, 2013. 19
Meir, U., Minzer, D., and Oshman, R. Can distributed uniformity testing be local? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing.
PODC, pp. 228 237, 2019. 3
Jowhari, H., Saglam, M., and Tardos, G. Tight bounds for lp samplers, finding duplicates in streams, and related problems. In Proceedings of the 30th ACM SIGMOD- SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pp. 49-58, 2011. 25
Metwally, A., Agrawal, D., and Abbadi, A. E. Duplicate detection in click streams. In Proceedings of the 14th international conference on World Wide Web, WWW, pp. 12-21, 2005. 25
Kane, D. M., Nelson, J., and Woodruff, D. P. An optimal al- gorithm for the distinct elements problem. In Proceedings of the Twenty-Nint Ninth ACM AGGMOD-SIGACTSSIGAAY
Mitzemmacher, M. A brief history of generative models for power law and lognormal distributions. Internet Math., I (2):226-251, 2003. 2
12

---

On Fine-Grained Distinct Element Estimation
Mitzenmacher, M. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural In- formation Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurlPS, pp. 462-471, 2018. 3
Sarawagi, S. and Bhamidipaty, A. Interactive deduplica- tion using active learning. In Proceedings of the Eighth ACM SIGKDD International Conference Knowledge Discovery and Data Mining. pp. 269-278, 2002. 25
Shukla, A., Deshpande, P., Naughton, J. F,, and Ramasamy, K. Storage estimation for multidimensional aggregates in the presence of hierarchies. In VLDB 96, Proceedings of 22th International Conference on Very Large Data Bases, pp. 522-531, 1996.
Mitzenmacher, M. and Vassilvitskii, S. Algorithms with predictions. In Roughgarden, T. (ed.), Beyond the Worst- Case Analysis of Algorithms, pp. 646-662. Cambridge University Press, 2020.
Tarui, J. Finding duplicate and missing item in stream. In Theory and Applications of Models of Computation. 4th International Conference, TAMC, Proceedings, pp.
Monge, A. E. and Elkan, C. An efficient domain- independent algorithm for detecting approximately dupli- cate database records. In Workshop Research Issues on Data Mining and Knowledge Discovery, DMKD 1997 in cooperation with ACM SIGMOD, 1997. 25
128-135, 2007. 25
Tejada, S., Knoblock, C. A., and Minton, S. Learning Hemmai-independert string transformation weights for high accuracy object identification. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 350-359, 2002. 25
Muthukrishnan, S. Data streams: Algorithms and appli- cations. Found. Trends Theor. Comput. Sci., (22), 2005. 25
Padmanabhan, S., Bhattacharjee, B., Malkemus, T., Cranston, L.,, and Huras, M. dineiiiiimnsional cluster- ing: A new data layout scheme in DB2. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 637-641. ACM, 2003. 1
Wang, D. and Wang, P. On the implications of zipf's law in passwords. In Computer Security ESORICS 2016 21st European Symposium on Research in Computer Security, Proceedings, Part I, volume 9878, pp. 111-131. Springer, 2016. 2
Pagh, R., Stöckel, M., and Woodruff, D. P. min-wise hashing optimal for summarizing set intersection? In Proceedings of the 33rd ACM SAGMOD-SIGACT-SICN Symposium on Principles of Database Systems, PODS,
Wang. D., Cheng, H., Wang, P., Huang, X., and Jian, G. Zipf's law in passwords. IEEE Trans. Inf. Forensics Secur, 12(11):2776-22) 2791, 2017. 2
pp. 109-120. 120, 2014. 18, 20
Woodruff, D. P. and Zhang, Q. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Sym- posium on Theory of Computing Conference, STOC, pp. 941-960, 2012. 1, 2, 4, 18, 19, 23
Palmer, C. R., Siganos, G., Faloutsos, M., Faloutsos, C., and Gibbons, P. B. The connectivity and fault-tolerance of the internet topology, 2001.
Prasad, A., Balakrishnan, S., and Ravikumar, P. A unified ap- proach to robust mean estimation. CoRR, (bb//1997,00977, 2019. 30
Woodruff, D. P. and Zhang, Q. An optimal lower bound for distinct elements in the message passing model. In Pro- ceedings of the Twenty-Fifth Annual ACM-SIAM Sympo- sium on Discrete Algorithms, SODA, pp. 718-733, 2014. 1, 2, 4, 5, 6, 15, 16, 18
Raskhodnikova, S., Ron, D., Shpilka, A., and Smith, A. D. Strong lower bounds for approximating distribution sup- port size and the distinct elements problem. SIAM J. Comput., 39(3):813 842, 2009.
Woodruff, D. P. and Zhou, S. Tight bounds for adversarially robust streams and sliding windows via difference estima- tors. In 62nd IEEE Annual Symposium on Foundations of Computer Science FOCS, pp. 1183-1196, 2021.
Resnick, P., Jacovou, N., Suchak, M., Bergstrom, P., and Riedl, J. Grouplens: An open architecture for collabo- rative filtering of netnews. In CSCW '94, Proceedings of the Conference on Computer Supported Cooperative Work, pp. 175-186. ACM, 1994.
Zipf, G. K. The psycho-biology of language: An introduc- tion to dynamic philology. Routledge, 2013. 2
Rhodes, L. Insights from engineering sketches for production and using sketches at scale, 2023. URL htttttsss/simmooe www.bberkkeeyyco heaamonns.errellly.cca/alleeeeee lee- tee-thooee--yhhoo-nn---000
13

---

On Fine-Grained Distinct Element Estimation
A. Preliminaries
For a positive integer n > we use the notation [x]] to represent the set (1,2,.... nt.. We use polylog(n) to denote a fixed polynomial in log n.
For vector R", define Fo(v) Ki [n]] is + 0) and Fi(e) = |uz| +... + |va)- For random variable X, use EE [X] to denote its expectation and V [X] to denote its variance.
Definition A.1 (Zipfian distribution dataset). We say sequence X = fa1,..., ,n. follows Zipfian distribution with exponent if there exist parameters C₁ C2 > 0 such that for any index i, we have C1 S
Recall the following definition of the squared Hellinger distance.
Definition A.2 (Squared Hellinger distance), For two distributions P and Q with probability density functions f and respectively, defined on a space X, their squared Hellinger distance is defined by
1 / (Vilt)- ()(P -
dx
It can be shown, c.f., Lemma B.3 in Section B, that the squared Hellinger distance between a function on two random variables is a lower bound on informally the mutual information between one of the random variables and the corresponding value the function on that random variable.
Communication complexity. We now recall some preliminaries from communication and information complexity.
Definition A.3 (Entropy, conditional entropy, mutual information). Given a pair of random variables X and Y with joint distribution p(x,2) u) and marginal distributions p(x) and p(y), the entropy of is defined as ((X) == - -Ea p(xx) log p(r)( ply) The mutual information is I(X;Y) = H(X) The conditional entropy is (Y) == - - p(z, y) log p(a.g)
H(XIY) Ex.y p(a,, y) log p(x.y)
p(*)p(y)'
Definition A.4 (Information cost). Let II be a randomized protocol that produces a (possibly random) transcript
[[ ,x) on imputs X1,..., Xr drawn from a distribution μ.. The information cost of with respect to p I(P). .... Pr; II(),....... Pr)).
Fact A.5 (Information cost to communication complexity). For any distribution p. and failure probability å E (0, 1), the communication cost of any randomized protocol for μ on problem f that fails with probability ö is at least the information cost of f under distribution and failure probability 5.
Definition A.6 (Conditional information cost). Let IT be protocol on ((x,)), ~ for ~ X and y ~ Y, where is mixture of product distributions on X" x Y x R and R ~ R is a source of randomness. Then we define the conditional information cost of II with respect to by I [xx, ()
Definition A.7 (Conditional information complexity). Given a failure probability 8 E (0, 1) and a mixture n of product distributions, we define the conditional information complexity of f with respect to 1j as the minimum conditional information cost of protocol for f with failure probability at most 6, with respect to n,, i.e.,
c min (xi, Y))R)
where the minimum is taken over all protocols TI with failure probability at most on the distribution
Lemma A.8 (Proposition 4.6 in (Bar-Yossef Yossef et al., 2004)). Let μ be a distribution on X x Y x. If is a mixture of product distributions on X x Y x R such that the marginal distribution on X x y is μ. then the information cost of a function f with success probability 1 8 on i is at least sff)
Fact A.9 (Chain rule). Given discrete random variables X,Y Y, Z, then
I(X,Y;2) I(X; 2) I(X;YIZ).
Fact A.10 (Maximum likelihood estimation principle). Let X E X and Y E y be randomly relected.from some underlying distribution μ. Then there exists a deterministic function Y + X with error d < 1 -
Definition A.1. For a vector y E X", let j E [n]] and x E X. We define Embed j. x)) to be the n-dimensional vector y with its j-th coordinate replaced by x, i.e., for z Embed(y. J. x), we have 2, = ys for + and 2j = x.
14

---

On Fine-Grained Distinct Element Estimation
Definition A.12 (Decomposable function). Let f x + 10 be a function. Then we say I is g-decomposable with prim- itive h if there exist functions g: [0, - {0, 1} and h : X + {0, 1} such that f(x. (h( y1). y1)...., ,,((,, yn)) Definition A.13 (Collapsing distribution). Let f X - {0,1] } be g-decomposable with primitive h. We say that (w, 2) E X is a collapsing input for f ifr every j E [n] and x. E X, we have (Embed(w..) x), Embed(z, j. = h(xr v)- We call a distribution y on X" a collapsing distribution for f if every (w, 2) in the support of μ is a collapsing input. Theorem A.14 (Direct sum, Theorem 5.6 in (Bar- Yossef et al., 2004)). Let f: X -> {0.1) 1) be a decomposable function with primitive h and let ( be mixture of product distributions on X x D. Let 17 =
5" and (xx,y), 1). Then if the distribution of (x. y) is a collapsing distribution for f. we have C 2 n c(C)
A.1. Technical Overview
In this section, we describe the intuition behind our algorithms and lower bounds for the distributed distinct elements estimation problem.
A. PROTOCOLS FOR DISTRIBUTED DISTINCT ELEMENT ESTIMATION
We first describe our general protocol for the distributed distinct element estimation problem across general ranges of Fo(S), the number of distinct elements in the dataset S that is the union of all items given to all servers, i.e., Theorem 1.1.
Constant-factor approximation. As a standard subroutine, our algorithm first computes a constant factor approximation to the number of distinct elements. Recall that this is done by subsampling the universe [r] at less and less aggressive rates. The a servers jointly set Sn = [r>] and for each i 2 1, the servers use public randomness to jointly sample each element of S into S. with probability 1. For example, the expected number of elements in S is ğ and so forth. The servers initialize i = [log n and send all of their local items that are contained within St to a designated server, which is marked as coordinator. They then send all of their items that are contained in S and so forth, until the coordinator sees (1) distinct elements across the entire set of items sent from all servers. Using a standard expectation and variance technique, it follows that rescaling the number of distinct elements seen by the coordinator by f. where p is the sampling probability of the universe induced by S., a constant- factor approximation to (S). The total communication used by this protocol is O (a n) for the a parties to report the identities of O (1) items across the sets S,, S before the algorithm terminates, combined with an additional log log n overhead to handle naïve union bound over at most O (log possible such sets, i.e., requiring the coordinator to see O(log log n) distinct elements.
(1 + E) -approximation. We note that a similar approach can be used to achieve a protocol with O ( log n log log n) total communication. Specifically, instead of stopping at a level where the coordinator sees ((1) unique items, the servers can choose to abort at a later time, in particular when the protocol samples down to a level where the coordinator sees @ (1) distinct elements. We show that the resulting estimator that rescales the number of distinct elements by the inverse of the sampling probability is an unbiased estimate the number of distinct elements, and moreover that the variance is sufficiently small due to the number of samples. Hence by standard Chebyshev argument, it follows that we can achieve a (1 + apaproxximaioon to the number of distinct elements. We emphasize that both the constant-factor and (1 + -pprrxiiiioiiittonnnn subsampling approach is standard among the distinct elements estimation literature, e.g., (Bar- Yossef et al., 2002; Kane et al., 2010; Woodruff & Zhang, 2014; Braverman et al., 2018; Blasiok, 2020).
However, the concern is that each of the a parties can send f (++) items, resulting in ft (+² items being sent across all parties. Indeed, in the hard instance of (Woodruff& & Zhang, 2014), constant fraction of items appear on a constant fraction of servers, so the protocol would actually use l (%) communication.
On the other hand, when the number of pairwise collisions is smaller than a². Fo(),, then the number of items that are redundant across multiple servers must also be smaller. We show this intuition translates to improved bounds for the same algorithm. That is. we show that when the number of pairwise collisions is B Fo(S) for some parameter 33 E [1, al.. then on average, each coordinate can appear across vB servers. Thus, the above protocol would send the identities of O items, resulting in total communication O (a log n + z4 logn).
Finally, we remark that when the total number of items is less than 22 i.e., Fo(S) without any sampling at all. Moreover, since the algorithm will eventually terminate at a level where no sampling is performed if there are no previous levels with e (+)) distinct elements given to the coordinator, then the same algorithm
< 1 g then the same analysis suffices
15

---

On Fine-Grained Distinct Element Estimation
suffices for this case. That is, our algorithm can obliviously handle all regimes of Fo(S), i.e., it does not need the promise of 2 as part of the input.
whether (S) 2 2 Fo( <
Handling a smaller number of collisions. We now describe how the guarantees of Theorem 1.1 can be further improved when the number of pairwise collisions is small. Note that (S) = (i()) D. where D is the excess mass across all servers, which we define the excess mass of coordinate j E [ni] in vector u E R to be max(0, Vi - 1) and the excess mass of e to be the sum of the excess masses across all of its coordinates. Note that D is upper bounded by the number of pairwise collisions C. Thus as a simple example, if we were promised C S cFo( then it would suffice for the a parties to compute Fi (5), which can be done in O (ar log n) bits of communication.
More generally, for C' < J. it is possible to efficiently estimate D without needing to send all items. In particular, given the 100C promise that there are at most C' pairwise collisions, we can estimate D by sampling the universe at a rate 2"x²,, where X is a constant-factor approximation to (S)) Again by a standard expectation and variance argument, it follows that the excess mass observed by the coordinator across the items sent at this level by all players, scaled inversely by the sampling probability, is an additive & (S) approximation to D. Since (S) = (i) - D and the players can compute Fi (i() exactly, then this provides a (1 e) aappooxmmation to Fo(S), as desired. The expected number of items sent by all items is which can then be translated into a concentration bound using Markov's 's inequality.
then O
2Z Pa
1.1. LOWER BOUNDS FOR PAIRWISE COLLISIONS
We now describe our techniques for showing that the number of pairwise collisions is an inherent characteristic for the complexity of the distributed distinet elements estimation problem. We first describe our lower bound in Theorem 1.3 for a large number of pairwise collisions. We then conclude with brief intuition for our lower bound for the distributed duplication detection problem in Theorem 1.5, which immediately gives our lower bound in Theorem 1.4 for a small number of pairwise collisions.
Large number of pairwise collisions. The starting point for our lower bound in Theorem 1.3 is problem called SUM DISJ, introduced by (Woodruff & Zhang, 2014) in the coordinator model. We note that the coordinator model of communication requires messages to go from server to the coordinator or from the coordinator to a server. Up to small factors, this can model arbitrary point-to- point communication. Indeed, if server i wishes to communicate to server j. then server can send its message to the coordinator and have the coordinator forward it to server j. This increases the communication by at most a multiplicative factor of 2 and an additive log a bits per message to indicate the identity of the recipient server.
In the SUM DISJ problem, there exist a players Pı,..., Pa with inputs Xiy..., Xa E (0.1) 1) and coordinator C and Y E 10,4 The vectors X,,..., X., Y are grouped into i blocks x(",, y for i E [a] and j E [4] each with L coordinates. The input to each block of X1 and Y are first generated as an instance of two-player set disjointness, so that there are blocks of set disjointness, each with universe size L., Recall that on a universe of size L,, the two-player input of set disjointness is as follows. First, for each i E [4], i is given X, with probability 1. otherwise i is given to Y with probability 1. otherwise i is not given X1 or Y with probability 3. Then for a special coordinate e chosen uniformly at random from [4]. the allocations of are reset. Then with probability 1. c is given to both players and otherwise with 2. c is given to neither player. The inputs X Xa are then generated conditioned on the value of Y, so that each pair (X,, Y) forms an input to two-player set disjointness. We define xI yū) = 0 if the instance is disjoint and DISJ ()) y() = otherwise. The output to SUM DISJ(X) Xa. Y) is then Σ. E D) y() (Woodruff & Zhang, 2014) show that approximating SUM - DISJ(X,,.... X.. Y) up to additive error O (Vat) requires I))tT. communication.
probability 1
The reduction of Fo approximation from SUM - -DISJ is then as follows. Given an instance Xi,..., Xa. Y of SUM - DISJ, the coordinator creates the indicator vector Z corresponding to [tL] \ Y. then follows that for = O (+ا and tL= = e (+), ) a (1 + apprroxiimtaionnnn to [X, +... + Xa + Z) suffices for the coordinator to determine SUM DISJ(XI..... X., Y) up to additive error O (Vol), given Y.
Moreover, we observe that due to the distribution of set disjointness where each coordinate is given to each player X, with probability at least? }. then with constant probability, a constant fraction of the items are given to a constant fraction of the players. That is, with probability at least 0.99, we have that ② (+) coordinates in the frequency vector X1 + ....t + Xa + Z
16

---

On Fine-Grained Distinct Element Estimation
have frequency ((a).
In turns out that for 3 < a, can embed the same problem across 3 players. Similarly, for Fo(s) 0 (5²) with
Fo(s) = M(a), it follows that for t O Fols) and tL (FF(ss)) a (1 apprroxxiatiionn Fo(X1 +... Xo + 2)
suffices for the coordinator to determine SUM DISJ(XI,............ ..s,,, Xa. Y) up to additive error O (Vat), given Y. Putting
these observations together, we obtain Theorem 1.3.
Small number of pairwise collisions. We first observe that our hardness result for the distributed duplication detection problem implies that any protocol that identifies whether there are fewer than (1 6)- C duplicates or more than (1 +e) C
duplicates requires C22
Fo(s)
communication for C 2 _. Moreover, the hard instance of Theorem 1.5 places the C
pairwise collisions across unique coordinates, so that Fo( = (S) - C. The a players can use O (log 4) = O (C)
bits of communication to compute Fi (i( exactly. Thus, we observe that a multiplicative (1 + a)aaproxiimation to Fo(S)
ultimately translates to a multiplicative
E-Fa(S) -pprroximation to in the hard instance of Theorem 1.5. We then
reparameterize the hardness statement to show that a multiplicative (1 s: FotS)
-aprroximation to C approximation
C
requires 5 (2)))(3)) communication. It thus remains to show Theorem 1.5, which we now describe.
A.1.3. DISTRIBUTED DUPLICATION DETECTION
Our starting point for the proof of Theorem 1.5 is noting that for C = E, 0, and 2, the problem becomes the decision problem of whether there exists at least a single coordinate that is duplicated or not across two sets. Thus, a natural candidate to consider is the set disjointness communication problem, e.g., (Chakrabarti et al., 2003; Bas-Yo et al., 2004), where two players each have a subset of [n]] and their goal is to determine whether the intersection of their sets is empty or non-empty. See Figure 3 for an example of possible set disjointness inputs for each case. Set disjointness requires total communication (2n) when the sets of each player have size ((n). and by a simple padding argument on a smaller universe, i.e., adding dummy elements that are never included in the players' sets, it follows that (?(s) communication is lower bound when each set has size ((s)..
Handling general a. We first generalize to a players, achieving a qualitatively similar statement to that obtained via a simple reduction from set disjointness in the coordinator model, which is a problem studied in (Braverman et al., 2013). It turns out for the approximate version of the problem we will not be able to use (Braverman et al., 2013) because we will need multiple instances of variant of promise set disjointness to argue about the number of duplicates created.
The usual notion of promise multiparty set disjointness is that there are a players who each have a subset of [n]] of size and their goal is to determine whether or not there exists a common element shared across all a sets. Furthermore, the generalization of existing lower bound techniques (Chakrabarti et al., 2003; Bar- Yossef et al., 2004) requires that if there is not a common element shared across all a sets, then the players have the promise that all of their subsets have empty pairwise intersections. That is, no element is even shared across two sets. Unfortunately for the purposes of the lower bound, there exists a simple protocol that only requires O (s log n) bits of communication: two of the a players simply exchange their sets (and in fact there is a more efficient way to determine if their sets are disjoint (Hástad & Wigderson, 2007)). If there is no intersection in their sets, then the intersection across all sets is empty. Otherwise, if their intersection is non-empty, then by the promise of the multiparty set disjointness input, the intersection across all a sets must be non-empty. Thus, it would be impossible to achieve the desired M(as) lower bound using the usual notion of promise multiparty set disjointness.
Observe that the simple protocol results from the promise that if there is not a common element shared across all a sets, then the players have the promise that all of their subsets have empty pairwise intersections. For the purposes of duplication detection, this requirement is not necessary. Instead, consider variant of multiparty set disjointness where either all sets are pairwise disjoint, or there exists single pair of sets that have non-empty intersection. In fact, we shall require our variant to be inherently distributional, uniform on each half of the universe (but not uniform on all pairs of elements of the universe), for the purposes of ultimately composing with a distributional communication problem to have an embedding from two players to a players while still retaining a sufficiently high entropy.
Then, intuitively, for each coordinate j E [n], the a parties must determine whether their input vector for j is 02, the
17

---

On Fine-Grained Distinct Element Estimation
elementary vector e; for some [a), or the sum of two elementary vectors e, + e, for some 1 S a < b < a. By comparison, the previous version of promise multiparty set disjointness simply required differentiating between 0º, e; for some i E [a], or 1 which has much larger gap, i.e. larger by multiplicative factor of l(()). Formally, this translates to a smaller gap by a multiplicative factor of (Q(a)) in the squared Hellinger distance of the protocol between the imputs of the YES and NO cases. We can then use similar arguments as in Bossef et al., 2004) to relate the squared Hellinger distance to the information cost of a correct protocol. Our argument thus achieves tight bounds, avoiding the extrancous multiplicative factor of M(x)) overhead that would have resulted from using promise multiparty set disjointness.
Handling general C and &. Handling general C' C'and seems significantly more challenging. A standard approach for achieving lower bounds with a 3b2 dependence is utilize the Rap-Hamming communication problem (Indyk & Woodruff, 2005), in which two players Alice and Bob receive vectors x, y E {0, 13", respectively, for / O ( (+²). Their goal is to determine whether A(x.y) y) S 5 vt or A(x, y) 2 2 + Vl, where (x. y) denotes the Hamming distance between x and y. It is known that the Sap-Hamming problem requires 52 (2²) bits of communication (Chakrabarti & Regev, 2012).
Unfortunately, it is not known how to extend the Gap- Gap-Hamming problem or its variants (Pagh al., 2014; Braverman et al., 2016) to the multiplayer communication setting. To circumvent this issue, previous works, e.g. (Woodruff & Zhang, 2012), that require Hup--amming-typa lower bounds for multiplayer communication protocols used a composition of Gap-Hamming with a multiplayer communication problem. Although using this approach (Woodruff' & Zhang, 2012) achieves a hardness of approximation for the number of distinct elements, which is the total number of items minus the number of duplicates if there are no k-wise collisions for k > 2, these results (Woodruff & Zhang, 2012; 2014) do not translate a hardness of approximation in our case. Nevertheless, we can use the composition approach in our case, the natural candidate is the multiplayer pairwise disjointness problem.
To that end, we define the composition problem GapSet as follows. The "outer" problem will be the GapAnd variant of Gap-Hamming while the "inner" problem will be the multiplayer pairwise disjointness problem. We first generate two vectors x, y E {0, 1} for / = O (++) In the YES case, we have (x > 7 + c vi for some constant e >> 0. In the NO case, we have (x 2 1 c. Vt. However, the vectors x, y will not be given any of the players. Using x, we instead generate vectors (1), ..... u(*) e {0, 10.t to give the a players. Each vector (f)) is partitioned into t blocks of size n. For j E [m]] the j-th block of all vectors u1)), ..... u(a) will encode a separate instance of multiplayer pairwise disjointness. If = y/ = 1, then there will be some "special" coordinate that is shared among two parties across the j-th block of the input vectors to the players, i.e., j-th instance of multiplayer pairwise disjointness. Otherwise, if x, = 0 or y = 0 (or both), then no coordinate is shared among multiple parties in the j-th instance of multiplayer pairwise disjointness. The goal of the a players is to distinguish whether (1) there exist at least 4 + c vi blocks that have some pairwise intersection, or (2) there are at most 1 + c. vi blocks that have some pairwise intersection.
f
Intuitively, the GapAnd lower bounds show that lt()) communication is needed to solve GapAnd. However, to recover each coordinate of x and y, the players must essentially solve an instance of multiplayer pairwise disjointness, which requires (()) communication, leading to a lower bound of ((nt) overall communication for the GapSet problem.
The reduction to duplication detection is then relatively straightforward. For C O (+). we choose & to be O(C) and n to be Ω ( (0e) ). so that 2(nt)= = M((s)). For the case where C 52 (+2), ) we instead set t = 1 and n = 2 (2#), which gives the desired ((xt)= = Ω (cse ) communication lower bound. However, the number of duplicates in this distribution is not
correct. Thus, we copy the instance θ (G) times to account for this. It then remains to prove the hardness of the GapSet problem.
Hardness of GapSet. A natural approach for showing that the information cost of multiple instances of a communication problem is the sum of the information costs of each instance of the communication problem, is the direct sum approach. The approach generally proceeds by embedding multiple independent instances of the inner problem into coordinates of an outer problem to show the hardness of the composition. For example, Bossef et al., 2004) views set disjointness as the n-wise OR of the AND problem across a players and uses the direct sum framework to show that since each AND problem requires (1) information, then set disjointness requires 2(1)) information. However, the direct sum approach is generally used for composition problems where the outer problem is sensitive to changes in the input - in the example above, the OR problem has different values for 0" and for any elementary vector e, with j E [n]. Our outer problem GapAnd does not necessarily satisfy this condition and so it does not seem that we can apply a direct sum argument.
Instead, we take the reverse approach by starting with the outer problem in the composition and using to solve the inner
18

---

On Fine-Grained Distinct Element Estimation
problem, which is an approach used in (Woodruff & Zhang, 2012) but for very different multiplayer communication problem.
For each j E [t), we let Dj = I O أررر so that the GapAnd problem is simply to determine whether |Dy| 2 + C vt or 12yl f c. VT. It is known that any protocol IT that solves GapAnd must reveal (())) information about D1...., Dz. In particular, this implies that there exist (tt)) coordinates
[t] such that conditioned on the previous values Di..... D the protocol reveals (2(1) information about Dj; we call such coordinate an informative index. The goal is then to show that for any informative index, the protocol II must reveal (()) information, due to the hardness of the multiplayer pairwise disjointness problem.
Consider a hard-wiring of a specific instance V of the multiplayer pairwise disjointness problem on an informative index j E [t]. The a players can fix the other coordinates of the GapSet before the j-th block and then plant V on the j-th block. Because the protocol reveals (11) information about Dj. this translates an (2(1) additive advantage over random guessing by using the maximum likelihood estimator. Morcover, note that the conditioning of the special coordinate in the multiplayer pairwise disjointness can only change the conditional information cost by an additive logarithmic factor. Hence, we obtain a protocol II' that can be used to solve multiplayer pairwise disjointness, which requires ((n) information. Then summing over the (t) informative indices, it follows that the information cost of II for GapSet is Q(nt).
A.2. Extension to Streaming Algorithms
Motivated by the connection between distributed algorithms and streaming algorithms, we also consider parameterized algorithms for the distinct elements problem in the streaming setting. In the streaming setting, a low memory algorithm is given a single pass or a small number of passes over a stream of items, and should output a (1 + 8 appproxxmtationnn to the number Fo of distinct items at the end of the stream with constant probability. We consider insertion-only streams.
We choose to parameterize the complexity in terms of C, the number of coordinates i E [n] with frequency f: 1. In situations in which the data is Zipfian, it may be the case that C is small compared to Fo, as only few items may occur more than once. We note that without parameterizing by C, there is an S (2) + llogn) bit lower bound for any constant number of passes (Jayram & Woodruff, 2013). We, however, are able to give a two-pass streaming algorithm using O(C + 1/e) memory, up to logarithmic factors, and we also prove a matching Ω (C + 2) lower bound for any constant number of passes. For one-pass algorithms we are able to achieve O ( (c) bits of space, up to logarithmic factors, also showing that one can bypass the Ω (1²) lower bound for C < 1/2. In fact, in all of our results, we can replace C' with the number of items with frequency strictly larger than 1, times the minimum of 1 and 1 which is especially useful if Fu > 22. 2%
Our two-pass streaming algorithm is based on computing the E noorm of the underlying vector, which is just the stream length since we only consider insertions of items, and then subtracting off an estimate to the contribution of items with frequency strictly larger than 1, which we call outliers. We then add back in an estimate to the total number of outliers. We can assume Fu = θ (3)) by subsampling the universe items at O (log n) scales to reduce Fu to value in θ (+) ) and preserve its value up to & (for this discussion let us assume Fo is at least 1 s/e² to begin with). We observe that for items that have frequency smaller than 2t. their total contribution to the l f--ormm is 1. they can be ignored as Fo = θ (+)) For items with frequency sufficiently large, we can identify them all using a CountSketch data structure (Charikar et al., 2002) with O (C + !) buckets, and thus this amount of memory up to logarithmic factors. Further, we can obtain an unbiased estimate to their sum with small enough variance by adding their individual CountSketch estimates. Finally, there are items with "intermediate frequencies" for which we cannot find them with CountSketch for these we instead subsample the universe elements, making the surviving universe elements with intermediate frequencies "heavier", since the total Fo has gone down and thus the noise in each CountSketch bucket is smaller while the frequency of an item with intermediate frequency has remained the same (note that we subsample universe elements rather than stream items). We identify the surviving universe elements with intermediate frequency and scale back up by the inverse of the sampling probability to estimate their contribution to the l norm.
One issue is that for items with intermediate frequencies, we need to subsample at multiple geometric rates, and in order to avoid over-counting we need to learn their frequency counts exactly, which we accomplish with a second pass. However, if we were to instead increase the number of hash buckets of CountSketch from O (C + !) to O (g), we could find all heavy hitters in single pass. Interestingly, for our single pass algorithm, we can also use methods for robust mean estimation (Prasad et al., 2019) applied to the values of our CountSketch buckets to estimate Fg. Indeed, we can view the few CountSketch buckets which contain an outlier as the corrupted samples in robust mean estimation algorithm. This
19

---

On Fine-Grained Distinct Element Estimation
allows us log n factor from the number of CountSketch tables. We give these results in Appendix D.
B. Communication Game Lower Bound
In this section, we define and analyze the communication complexity of the GapSet problem. Recall that GapSet is the composition the GapAnd problem on & coordinates with the multiplayer pairwise disjointness problem on n coordinates. The intuition is that GapSet requires ((nl)) communication because the outer problem GapAnd requires (?(1) communication and each inner problem of the multiplayer pairwise disjointness problem requires (nn) communication. The formal proof significantly more involved. For starters, communication complexity is not additive but information costs are, require number of preliminaries for information theory, which recall in part in Section A.
We first formally define the GapAnd problem, which serves as the "outer" problem in the composition problem GapSet, as follows:
Definition B.1 (GapAnd). In the distributional t-coordinate GapAnd problem GapAnd,, Alice and Bob receive vectors x,y E (0, 1)2 generated uniformly at random. Let >> 0 be a constant. Bob's goal to determine whether the imput falls into the cases:
In the YES case, for least? + 1 vt coordinates j E [t], we have xj 1/j 1.
16
In the NO case, for at most
1 vt coordinates j E [t], we have 2j yj 1. Otherwise if neither the YES case nor the NO case occurs, then Bob's 's output may be arbitrary.
T6
It is known that any protocol that obtains a constant advantage over random guessing reveals 22()) information about the input vectors.
Lemma B.2. (Chakrabarti et al., 2012; Pagh et al., 2014; Braverman al., 2016) There exists a sufficiently small constant ō for which any private randomness protocol 11 for GapAnd, that succeeds with probability at least 1 21(1) over inputs x, the private randomness of II and public randomness R satisfies
xx. =
Recall that in the set disjointness communication problem, e.g., (Chakrabarti et al., 2003; Bossef et al., 2004), two players each have a subset of [n] and their goal is to determine whether the intersection of their sets is empty or non-empty. We define a variant of set disjointness as our "inner" problem. See Figure for an example of possible set disjointness inputs for each case.
0
0
0
0
0
0
0
(a) YES instance
(b) NO instance
Figure 3: Examples of YES and NO instances of the set disjointness problem for a = 2 players.
We show that any protocol for GapSet, with constant & requires (nn) communication. To that end, we first recall the following structural properties from (Bar- Yossef et al., 2004):
Lemma B.3 (Lemma 6.2 in (Bar-Yossed variable with uniform distribution in {X, }. If Z is independent of both f(X) and f(Y), then 1 [(2; f()) 2 fv), where Xx denotes the distribution of on X.
al., 2004)). Let f(X) and f(Y) be two random variables and let 7 be random
Lemma B.4 Cut-and-Paste. e.g., Lemma 6.3 in (Bar- Yossef et al., 2004)). Let II be a randomized protocol, x, E X, and y E Y for some domains X, Y. Then h([lzy, Ug = h((Tary' l.
Lemma B,5 (Pythagorean Lemma, e.g., Lemma 6.4 in (Bar- Yossef et al., 2004)). Let II be a randomized protocol, a, X. and y, v E Y for some domains X, Y. Then h (Tlay, TT h22 (TTay T & 21 (Tzzy Tl
20

---

On Fine-Grained Distinct Element Estimation
Lemma B.6 (Lemma 6.5 in (Bar-Yossed et al., 2004)). Let II be randomized protocol with failure probability 5 E (0, for function f. Then for any two input pairs (a,, y) and (a' 1/) with f( y) * f( vf),, have he (Tany: uzyy ) 2 2v8.
Lemma B.7. Let 2 be an integer and let le E [a). Let II be randomized ox-arty communication protocol with inputs [a]] be any permulation. Then,
from (0, 3 for determining whether exactly coordinates are one and let [ax] -
La/k!
Σ h [og0 0o Ie.)) 2
1
Σ j=1
h (Il
(11),,
2k
where 1 =
[aji11 12 2k
Proof. Similar the proof of Lemma 7.2 in YosseY et al., 2004), prove the claim by using an induction argument on tree. Let a' be the smallest power of two such that I a' and let ø be any mapping that extends a permutation [a] + [a] in the natural way to a' coordinates, i.e., o(i) t(i) for E [a] and o(i) for i E (a,a'), Let I be complete binary tree of height log(a') with leaves labeled from o (1) to o(a') and internal nodes labeled with the leaves in their corresponding rooted subtrees.
For a, E [ar] with b - a + = k, let c= ط=ي Let = @x((a,l)) v (n((a,)) and w ex([e+1,6)) By an analogue of Lemma B.4 for a' -player communication games, we have that
h(Ilgo', I1,)) = h(II, Il
On the other hand, since the last a' - input coordinates are known by all players, we have
h[lge Il.) Ilw)
By the triangle inequality,
h[Tg.. IIo) + h(Tls, Iww) 2 Iw).
Thus by the Secbly--Shwwazziequuuaaa
n2 (I,, Iww S (Il,, + (Iloa, I.)))
Then by induction.
2(b - 1) Σ h (Ilgs [1,,) 2 h²2 h1lg= (Ioss,I
For a + 1, we can split the interval [0, al into at least
disjoint intervals of length k. Therefore,
La/k]
1
2 (1 lle:) 2
Σ
(1le,,
2k
j=1
where I, [a(j-1) 2k
+ 1, ad
2k
We now show that any protocol for GapSet,, requires ((n) communication for constant k: > 0.
Lemma B.S. The conditional information cost of any algorithm for Set that succeeds with probability 1 + f2(1) is 1(n).
Proof. We first use the direct sum paradigm by defining the NO distribution for the single coordinate SetWt,..t problem, which implicitly forms the NO distribution μ4 for SetDisj,.,- We use a random variable Q E [a] chosen uniformly at random, so that conditioned on the value of Q = E [a], we have that u is chosen from {0", c.) uniformly at random, implicitly defining the distribution Ç. Then <" the collapsing distribution that matches the distribution of Ho and so by Theorem A. 14, it suffices to show that the conditional information cost of IT with respect to Ç 2(1).
21

---

On Fine-Grained Distinct Element Estimation
To that end, have
1 [(T(()))(Q)
Σ a T(T((): i).
By Lemma B.3 and Lemma B.7
I(I(())
he2 ( le;))
0
Ln/k] h2 (Tlo, Nos 1t02s)
1
2a
By the correctness of the protocol μ and Lemma B.6, have that u(I( = -I(1). Hence, the conditional
information cost of any algorithm for SetDisjn, that succeeds with probability 2 + 2(() under the mixture distribution J tuo + 21 is ((2).
We now define the composition communication problem GapSet.
Definition B.9 (GapSet). In GapSet,,a,n.k the distribution & for the GapSet problem over t blocks each with n coordinates and & collisions for a players is defined as follows. The ar players receive input vectors u()),... ,u()) E {0, 13md such that the i-th player receives vector u(),, for all [a]. Let B = [g]] and f. == - The input generated by first drawing x,y E {0, 13 from GapAnd, and creating inpul vectors Jelajjj11)
For each j E [t], a special coordinate Zj E [m]] is selected uniformly at random.
x then the coordinate Zj is given random players, i.e., the protocol selects E indices that (3
uz (6 1.
B, i.e., ". I B, and sets uz,
o If yj = 1, then the coordinate Zj is given to k random players, i.e., the protocol selects k indices that are at least B + 1, ie., fjets..... ,35. 2 B 1, and sets u22
(b12-115
(1 1. 22
For all coordinates w E [n] with w + Z,. with probability 1 2. the protocol assigns w to a random player wj E [[]]. iee. it sets the (w)
Each vector v (1.)) n (2.) o... (a.)) and the a players' goal to determine whether the input falls into the cases:
In the YES case, the imput is generated from vectors x,y {0, 13' that are in the YES case for GapAnd,-
In the NO case, the input is generated from vectors x,y {0,1)' that are in the NO case for GapAnd,.
Otherwise if the input is generated from vectors x,y E {0, 13 that are neither in the YES or NO cases for GapAnd,,
then the a players' output may be arbitrary.
See Figure 4 for examples of possible inputs to GapSet.
1
O
O
0
1
0
0
0
0
O
0
0
0
0
(a) Small number of collisions instance
(b) Large number of collisions instance
Figure 4: Examples of input instances for GapSet problem for a = 2 players, f blocks, and n = coordinates on cach block.
We first show the mutual information between successful protocol for GapSet and set of auxiliary variables.
22

---

On Fine-Grained Distinct Element Estimation
Lemma B.10. Let II be a protocol that solves ,, with probability at least 0.99. Let {u(0) Hetal be an imput for GapSet,, generated from vectors y drawn from ,- Let M be the transcript of II on input {u()) kefo) and R. be a fixing of auxiliary random bits. For each j E [t]. let Dj- = [ 0 yyl. Then
R) R) I(;; Di,... D.
9(1).
Proof. Since the vectors x, y are an instance drawn from GapAnd,, then we have x) = y/; = if and only if D, = 1. Thus M any message produced by a protocol II that solves the distributional problem GapSet,, with probability at least 0.99 also solves GapAnd, with probability at least 0.99,
By Lemma B.2,
DI, D( 2 ():
A) BRR) = =.(t).
We define the following "guess" variant of the set disjointness problem, along with the input distributions D1 and D2. In the GUESS problem, there exists a fixed coordinate Z E [nx]. We define the distribution D (Di...., Dn)) as follows. For each i E [m]. Dj is random integer in [a)] All sites not equal to Dj have their i-th coordinate set to zero. With probability 2. the site D; has its i-th coordinate set to one; otherwise it is set to zero. We define D1 to be this distribution.
We then achieve the distribution D, by making the following modifications to D1. For coordinate Z, with probability 1 2' we set the Z-th coordinate of f _ random servers of index most 3 2 to and the remaining zero. In this case, we say X = 1. Otherwise, we set all of those coordinates to be zero and we say X = O. Similarly for coordinate Z, with probability 2. we set the Z-th coordinate of k - l random servers of index larger 3 = [ to one and the remaining to zero. In this case, we say Y = 1. Otherwise, we set all of those coordinates to be zero and we say Y = 0. In the GUESS variant, there is an additional party that observes the transcript of the communication protocol between Alice and Bob and must guess the values of X and Y. By a similar argument to Theorem 5 in (Woodruff & Zhang, 2012), we have:
Theorem B.11. Lei II be the transcript of any randomized protocol for GUESS on input V ~ >D2 with success probability (1). Then for (1), we have T[V; D, Z) = (m)). where information is measured with respect to DDz
The only difference is that the input distribution D: is slightly different than the input distribution for Theorem 5 in (Woodruff & Zhang, 2012), where all a servers have ones in the case the set disjointness input is a NO instance. By comparison, we only have k servers for l = O (1), so that the mutual information is 2(1) times the Hellinger distance between the all zeros vector and an elementary vector.
We now lower bound the mutual information for any protocol that solves GapSet. The proof follows exactly the same structure as Theorem 7 of (Woodruff & Zhang, 2012).
Lemma B.12. Let R be a source of fixed randomness and U = (uf())eto be an instance of GapSet,,a... For each j E [tl, let D and Z denote the outcomes of D and Z for the j-th block, respectively and let D and Z denote the outcomes across all j E [t). Then for any protocol IT that produces transcript (U) on input U that solves GapSet,.om..
with probability at least 3 + Q(1) satisfies I (U); UÍ Z) 2 M(nt).
4
Proof. Let (u()) Ne((a] be generated from vectors y, drawn from GapAnd,. For each j E [t], let X and ( denote the outcomes of X and Y for the j-th block, respectively, and define X and Y similarly. By Lemma B.10 and the chain rule, i.c.. Fact A.9, there exist lit) coordinates j E [t] such that ((x(1), Y M ((0))x((3) y(i)) 2(<0) = Q(1). We
define such an index j E [t] to be informative.
Now, we can write T(U(5);; M D2XI<0, y(5)), Z) as
Σ Pr (daa)))))
(w(ss), x(s)) y(a)) z(اا)) (d, (d
x T(U M D',2', (D(<)) x(<) y(<)) 2(<5)) = (d, x. y, =))
By definition of an informative index i, we have with constant fraction of the summands (d, x, y, 2) that
I(U(<5); M D2, 2, (D(()), x(5I), y(<3) イ(<)) (d, x. y, 2)) = 2(1).
23

---

On Fine-Grained Distinct Element Estimation
We say such ordered tuplets are good for an informative index j.
Observe that by independence of the distribution across the coordinates j E [n], we have
H(U(<)) 1',2", x y(u)) z(<))) ,(=)),((0))) = 21 M/ 2)) 2.
Now for an informative index j and (d, x, 2, that is good for
H(U(<)) M, z², (D(S)) ,x(5)) z((0)) ,((t) y(si) -(U(())) D z2, (D(s), ((50),((0)) (d, 2))
= [d, 2))
- 1(U(<)) M D',Z', (2(())) x(<)), yish, z(50) = (d. 1),
22 Q11.
For good (d, 2, y, for an informative j. we build a protocol I., that computes the GUESS problem on input D2 with probability 4 + (2) Let AI...., A be the inputs to the sites and let (Q, R) be the input for the predictor, where Q is realization of D and R is realization of Z. Then Jd has (j. d, x. y.2) hard-coded so that the k sites construct an input B for GapSet using the distribution Φb In particular, they set Bld) {Ai,..., Aa and then use private randomness to independently generate blocks j' * j, given the values of (d, x, y. z). Then by setting D Q and Z = RR for the predictor, the sites can run on input B.
Hence by Theorem B.11, we have
((M U(D,)) N
Σ
I(M(U):U()
U 2, U(<)))
informative
Σ
Σ
( ,x(x) ,(s)) = =(d, (,, v, x)
Pr
(d.2)))))
informative j good (d.a...))
x T(U(<0) M D', (D(<)), x(<s), y(so) أ(اح)ح = (d. (,,,,))
= =((!)).
Finally, we show the communication complexity of GapSet. Theorem B.13. Any protocol 1I that solves GapSet with probability at least 3 + +11 uses (2(tt) bits of communica- tion.
Proof. The proof follows immediately from Lemma B. Fact A.5, and Lemma A.8.
Using Lemma 1. we ultimately show Theorem 1.5 by designing a reduction with the appropriate values of n and é; we defer the proof to Section C.
C. Applications to Duplication Detection
In this section, we prove Theorem 1.5 well as describe additional applications to the duplication detection problem. Recall that in the duplication detect problem, the goal for the servers is to approximate the total number of duplicates, where a duplicate is defined to be coordinate j E [rx] that appears on at least two distinct servers. We first show that our communication game lower bound in Section B gives a hardness of approximation to estimating the number of duplicates. We then give an algorithm that shows that our lower bound is in fact, tight.
C.1. Motivation and Related Work
Database cleaning. The detection and elimination of repeated data is an important task for data cleaning and data quality in database management. Due to data entry errors, multiple accounts, varying conventions, or a number of other reasons, the same concept or real-world entity may correspond to multiple entries in database, which can often be the source of
24

---

On Fine-Grained Distinct Element Estimation
significant challenges for users of the database. For example, duplicated entries in database can lead to increased direct mailing costs because duplicated consumers may be sent multiple copies of the same catalog. (Chaudhuri et al., 2005) observes that duplicates can also induce incorrect outputs for analytic queries, such as the size of the overall consumer base, and thus lead to erroneous data mining models downstream. Therefore, significant effort and costs are spent on identifying and removing repeated items in a datahase.
The duplication detection problem is also known as the merge/purge, deduping, and record linkage problem (Fellegi & Sunter, 1969; Kilss& & Alvey, 1986; Bitton& & DeWitt, 1983; Monge & Elkan, 1997; Hernández & Stolfo, 1998; Sarawagi Bhamidipaty, 2002; Bilenko & Mooney, 2003) and in fact, a more general version of the duplication detection problem. known fuzzy duplication detection (Ananthakrishna et al., 2002; Chaudhuri et al., 2005), is often studied. In the fuzzy duplication problem, the goal is not only to identify the duplicated entries in a database, but also to identify sufficiently close entries in a database, which among other things can help account for human errors such as typos or missing information.
Techniques for the fuzzy duplication problem can largely be separated into supervised and unsupervised approaches. Supervised approaches generally use training data containing known duplicates to find characteristics that are then used to identify future duplicates (Cohen & Richman, 2002: Bilenko & Mooney, 2003). However, such approaches not only lack theoretical guarantees but also often encounter difficulties in finding effective training data that display the same distribution of duplicates observed in practice (Chaudhuri et al., 2005). (Sarawagi & Bhamidipaty, 2002; Tejada et al., 2002) addressed this shortcoming by using active learning to interactively update the training data, but the drawback is that their approaches require manual guidance to perform the updates. Unsupervised approaches generally use global thresholds for distance functions, such as the edit distance or the cosine distance, to detect duplicates, which induces poor recall- recall-precision tradcoffs (Hernández & Stolfo, 1998; Monge & Elkan, 1997; Chaudhuri et al., 2005) since individual fuzzy duplications may not follow the general global trends. For the standard duplication detection problem, one simple approach (Metwally et al., 2005) use Bloom filters (Bloom, 1970) to avoid communicating the full information of each entry. However, this generally requires communication linear in the size of the entire dataset.
Advertising commissions. As noted by (Metwally et al., 2005), related application of duplicate detection is to the task of advertising commissions by the middle party between advertisers and publishers. In typical scenario, an advertiser and a publisher generally arrange an agreement for a specified commission for each user interaction with an advertisement, such as clicking or watching an advertisement, completing a form, bidding on an item, or making a transaction. The publisher will then display advertisements, forms, or text links on its products, while using tracking information, e.g., referral codes, to monitor the traffic it directs to the advertiser's 's materials. Similarly, the advertiser will also use tracking information to monitor the traffic directed from each publisher to its site. Inconsistencies between the statistics claimed by the advertiser and the publisher are then resolved by an arbiter, third-party tracking entity called the advertising commissioner, who serves middle party who receives the traffic from the publisher and forwards it to the advertiser.
Because the publisher receives revenue proportional to the traffic that they direct to the advertising site, they can be incentivized to falsely increase the number of hits produced by their referral link, a process called click inflation (Anupam et al., 1999; Metwally et al., 2005). On the other hand, the advertising commissioner must report the true traffic directed to the advertising site and thus detect any click inflation that has occurred. By simplifying the traffic information to an identification number such the IP address, the problem for the advertising commissioner reduces duplication detection.
Duplication detection in the streaming model. Duplication detection has also been extensively studied in other big data models, in particular the streaming model (Metwally et al., 2005; Gopalan & Radhakrishnan, 2009; Jowhari et al., 201 1). In fact, (Muthukrishnan, 2005) explicitly ask the question of whether duplication detection could be performed in polylog(m) space, where m is the size of the data, e.g., the length of the data stream. The problem can be solved in O (log m) space in the random access model. For deterministic algorithms, (Tarui, 2007) showed that even if the streaming algorithm is allowed k passes over the data, Ω (m-//) memory is necessary. (Gopalan & Radhakrishnan, 2009) answered the question of (Muthukrishnan, 2005) in the affirmative by giving a randomized algorithm that uses O (log* (m)) bits of space for the duplication detection problem when the stream length is larger than the universe size. Without such a condition there is a strong (m)) memory lower bound. (Jowhari et al., 2011) finally gave tight upper and lower bounds, showing that the space complexity of the duplication detection problem is O(log
2 (m)) bits.
25

---

On Fine-Grained Distinct Element Estimation
C.2. Hardness of Duplication Detection Problem
In this section, we give our lower bound for the communication complexity of the duplication detection problem, which we recall is defined follows: let C be an imput parameter for the number of collisions and k be an input parameter for the number of players with mutual collisions. Let (0, 1) be an accuracy parameter. Suppose there exist players, each with samples. The goal is to identify whether there are fewer than C coordinates or more than (1 + E) C' coordinates shared among exactly k players.
Our approach is to reduce the problem duplication detection from the GapSet problem. We split the analysis into casework depending on whether O (/2) or C (1) However, we first require the following structural properties to argue distribution matching.
Fact C.1 (Stirling's approximation), For any integer k > O, we have
k sk ek
Lemma C.2. Let c > 0 be a constant. Let X be random variable drawn from the binomial distribution on t trials with
probability 3. Then we have
Pr x 1 <c. vi sc
Proof. We assume that is divisible by and define the interval
1= 1=(iEN) iENi t - --vvvii<
Note that if is not divisible by 4, we can perform similar analysis on 4 4
Let X be random variable drawn from the binomial distribution trials with probability 1. We bound the probability Pr(x E 1] = Eies Pr [X i]. Observe that we have
3
Pr Pr Pr[X=1]=
1)
Hence,
Pr X e
1 ( 1)1(t - i 1)!
- it-
Pr X -i-- 1]
3 iltt - i)!
3
-r so that Pr[X=11] < fo and PriX=1-1
Pr[X=i]
for < 1. Therefore, Pr [X = i] is maximized at
4'
We now upper bound (1/2) using Stirling's approximation in Fact C.1 to handle the binomial coefficients. We have
(11A) = (31/4)((14))
t!
+
(v2T (3t/4)31/4411 1/2
31/4) (v22(t/4)/4411/2=11
(3/4))) 35/4 (1/4)114
Hence, we have
1
8/4
3
31/4
e
Pr
X
4
2 2T (3/4) 30/4 (1/4)//4
1
2x Vi
2/i
26

---

On Fine-Grained Distinct Element Estimation
Therefore,
20v s
Pr[XeT| Σ EET
Pr -x Σ IET
C.
20i
2V
2/1
We first consider the case where C
g2.
Lemma C.3. Let C an input parameter for the number of collisions and be an inpul parameter for the rumber of players with mutual collisions. Let e E (0, 1) be an accuracy parameter such that C < 3. Suppose there exist a players, each with samples from some universe of size N (s)). Then any protocol II that with probability at least 0.99, identifies whether there are fewer than (1 c) C coordinates more than (1 + E) C coordinates shared among exactly is players requires ((ss) communication.
Proof. We first consider the setting where C< 2.2 Let 4C and = Q ((0) Let lu()) be instance of GapSet,, Recall that [u[] is generated from x,y E {0. 1)2 drawn from GapAnd,- For each j E [t], let D2 denote the indicator random variable for whether æj yj so that Dj 1 if zy yj and Dj otherwise. Note that Dj is Bemoulli random variable with parameter 7. Let D Σjen Dj. so that D is a binomial random variable with t trials and parameter 7.
Observe that 1 1i2 ei. so that a (1 + apappoxxxnotooon algorithm to the number of w-wise collisions will also determine 16 the number of coordinates j E [4] such that Dj 1. We have that Pr D 1 2 Vi 2 0.2. Thus have that with probability least I. II will be able solve GapSet Hence by Theorem B.13, II must use M(nt)) R(as)) communication.
T6
We next consider the case where C 3. The proof follows similarly to Lemma C.3 but also uses padding argument account for the number of collisions.
Lemma C.4. Let C be an input parameter for the number of collisions and k be an imput parameter for the number of players with mutual collisions. Let e E (0, 1) be an accuracy parameter such that C C -. Suppose there exist a players, each with samples from some universe of size N Mss. Then any protocol II that with probability at least 0.99, identifies whether there are fewer than () C coordinates more than (1 + C' coordinates shared among exactly k players communication.
requires Q
as Ce
Proof. Let = - and n = S as Let {v(i) JiEfal be an instance of GapSet,,o.n.t We then set ( to be copies of v() for each E [a]] that u (6) (+) o v(i) o... (t), For each j E [t]. we define D, to be the indicator random variable = 1 and Dj = 0 otherwise. Since {v(0) Jaea is generated from
for whether zj- Mj = 1, so that Dj = 1 xj x,y E (0, 1 drawn from GapAnd,, then Dj is Bernoulli random variable with parameter z. Hence for D = Ejett Dj. we have that D is binomial random variable with trials and parameter 1
Observe that T6 Vt 2 ef. so that a (1 + --aappooximtioonn algorithm to the number of k-wise collisions will also determine the number of coordinates j [t] such that D, 1. By Lemma C.2, we have that Pr [[D 1 2 1e vt 2 0.2. Thus we have that with probability at least 3 communication.
4, II will be able to solve GapSet, Hence by Theorem B.13, II must use
a(nd)= Ω (E
Putting Lemma C.3 and Lemma C.4 together, we have:
Theorem C.5. Let C' be an inpul parameter for the number of collisions, k be an input parameter for the number of players with mutual collisions, and E E (0, 1) be an accuracy parameter. Suppose there exist a players, each with s samples from some universe of size N = s2s). Then any protocol TI that with probability at least 0.99, identifies whether there are fewer than (1 e) C coordinates or more than (1 + +) C coordinates shared among exactly k players requires R(xs) communication for C - and Ω as communication for C 2 3.
Theorem 1.5 then follows from setting & 2.
27

---

On Fine-Grained Distinct Element Estimation
(1) For each player E [o), let S; be the set of items given to player
(2) For each j E [NV] sample j into a set U with probability p p= p= CEa
This is done by all players using public
randomness.
(3) For each i [o), let T; S.nu.
(4) Let v be a bit vector of size Cg
Sos for a sufficiently large constant Ç >> 0.
(5) While there are multiple items in UT, that hash to the same position of
(a) All players hash 7; into v and communicate the non-zero entries of their hash.
(b) For any z that does not map position of communicated by multiple players, remove from the remaining items, i.e., T, T, {x) for all i [o].
(6) Let D' be the number positions that are communicated by multiple players.
Output D' for the estimated number of collisions.
p
Figure 5: Distributed protocol for duplication estimation
C.3. Upper Bounds for Duplication Detection
In this section, we provide a short sketch of a distributed protocol for the duplication detection problem. The protocol uses standard techniques and is summarized in Figure 5. Given C 0 and an accuracy parameter (0, 1), the a parties must determine whether there exist least C' (1 + =) duplicates or at most C' (1 =) duplicates.
The protocol proceeds as follows. The parties first sample each item from the universe at rate p = + (dzz). That is, instead of considering the universe [N], they consider a universe U where for each i E [N], we have E U with probability Then each player only considers the subset of their items that are contained in U.
By standard calculations on the expectation and variance, it can be shown that if D' is the number of duplicates across the subsampled universe U, then Dr is an additive O (E) C' approximation to the actual number 1) of duplicates. That is, with probability 0.99, we have D' D S O (c) C. It thus remains to compute the number of duplicates in the universe U.
was By Markov's inequality, with probability at least 0.99, the total number of items in the universe U is at most Cg2 for some sufficiently large constant y. Let & be the event that the total number of items in the universe U is at most Ce so that for
Tes
(r 2 0.99. The players first hash their items into a bit vector of size Ce. for sufficiently large constant & > 0. We call an item E [N] isolated if it bashed into coordinate of that no other item is hashed Note that conditioned on E, the probability that each item is isolated is at least 0.999, for sufficiently large
The players then succinetly communicate the hashes of all their items as follows. For each E [a]. let N, be the number of samples that player i has that is contained in the universe U. To communicate their items, it suffices to use total communication
Σ Jog (Tas/Ce²) log II N₂
(os CE N₂
Cass/C22 78/Ce2
log II i=1
where the last inequality holds due to the constraint that conditioned on E, we have
708
+.....4 ...... NN, S C
Thus the total communication is at most
log (nas/C=2) (78/Co2)
a aolooaa O
788
=0
Yas log a
C
Cea
Note that the central server will immediately observe that any isolated item cannot be duplicated. On the other hand, there could be multiple items that are not duplicated, yet are sent the same coordinate in the bit vector v. By Markov's
28

---

On Fine-Grained Distinct Element Estimation
inequality, have that with probability least 0.99, half of the items that not duplicates isolated. It then suffices recurse.
That is, in each iteration É, suppose we have 2a08
remaining items that are not duplicated. Then running the above protocol, We have that E [ne]
C
the total communication in round is O yaas log
1 [ye-1]- Thus, in expectation, the total Then again by Markov's inequality and the fact that is
Ce
communication is geometric series that sums to O
youe log
Taclog
Cea
constant, we have that the total communication is O Theorem C.6. Given C and an accuracy parameter (0, 1), there exists distributed protocol for parties that
log Ce
determine whether there exist at least C E)+ duplicates at most C. (1 duplicates with probability at least ihd and
uses O log communication.
Proof. Let D be the number of duplicates across the parties and D' be the number of duplicates in the subsampled universe. Let D be the set of duplicates among the parties, so that D D. Let p be the probability that each coordinate in the universe is sampled. Then we have
E[D'|
E
Σx p= Dp,
ÍED
D'
so that E
Moreover, we have
V
D'
1
Σ
p
D
o (C
1
p
so that by Chebyshev's inequality, we have
D' p
D Se. (.CD) 2 0.99.
Pr
Now we note that if C
1000 or D 1000C, then simple 100-approximation to D suffices distinguish whether D C. +1+ or D C-C- E). Thus we assume T000 & D < 1000C, so that
D' D - s0-))s(())-o N 0.99.
Pr
It thus remains to compute the number of duplicates in the universe U. To that end, the players first hash their items into a bit vector v of size Cg for a sufficiently large constant g >> 0.
Eos
We call an item i [N] isolated it is hashed into coordinate of v that no other item is hashed to. Note that conditioned on E. the probability that each item isolated is at least 0.999, for sufficiently large ç. By Markov's inequality, with probability at least 0.99, the total number of items in the universe U is most 2as C that Pr [g] 0.99.
y0s for some sufficiently large constant y. Let & be the Cgz
event that the total number of items in the universe U is at most
The players then succinetly communicate the hashes of all their items as follows. For each E [a]. let N, be the number of samples that player i has that is contained in the universe U. To communicate their items, suffices to use total communication
Σ log (1as/C=*) log II
yas/ CC= N
/ass/CE# ys/Ce2
log II s=1
where the last inequality holds due to the constraint that conditioned on E, we have
708
N1 +.... NN, S C
Thus the total communication is at most
log (nas/Ce²) ys/CC22
a log a O
78
Yas log a Cea
=0
Ca2
29

---

On Fine-Grained Distinct Element Estimation
Note that the central server will immediately observe that any isolated item cannot be duplicated. On the other hand, there could be multiple items that are not duplicated, yet sent the same coordinate in the bit vector v. By Markov's inequality, we have that with probability at least 0.99, half of the items that are not duplicates are isolated.
The protocol is then performed recursively. Specifically, in each iteration é, suppose there remain duplicated. Then running the above protocol, the total communication in iteration & most Zrroa log for some constant >> O. Call iteration successful if "ee S Ve- that the above argument implies that each iteration is successful with probability at least 0.99. Thus we have
Tyos items that are not Ce
Cea
99
[ <
100 2 7--1 +
100 7h-
S 3
7--1-
Then the expected communication A₃ of iteration E + 1 is at most
TYyas log a
(2)
ryyas log a
E A
Cea
C=a
Thus, expectation, the total communication A a geometric series that sums O
yas log Ce
[ Σ E [
So
(20s
log
Ce2
Then again by Markov's inequality and the fact that y is constant, we have that the total communication is O
log Ca
D. Parameterized Streaming for Distinct Elements
In this section, we consider distinct elements estimation in the streaming model. Namely, there exists an underlying vector Rn and each update in a stream of length m poly(n) can increase or decrease a coordinate of x. The goal is to estimate ||ж||o within multiplicative factor
+)) at the end of the stream using space polylogarithmic in n. Moreover, known that w (+) bits of space is generally needed solve this problem. We now show that if the number of coordinates with frequency more than one is small, this lower bound need not hold.
We first require the following guarantees of the well-known COUNTSKETCH data structure from streaming. Theorem D.1. (Charikar et al., 2002) Let x E IR" and let with the vector x with the coordinates largest in magnitude set to zero. Then with high probability. for each i E [n]] COUNTSKETCH outputs an estimate &; such that
[ - - V6 llvll2.
Moreover; COUNTSKETCH uses O (blog" n) bits of space.
D.I. Robust Statistics
In this section, we present a streaming algorithm for distinct element estimation based robust statisties. We first recall the following statement from robust mean estimation.
Theorem D.2. (Prasad et al., 2019) Let P be any 2k-moment bounded distribution over IR with mean μ and variance bounded by o². Let Q be an arbitrary distribution and the mixture P. (1 P =Q. Given n samples from Pe, there exists an algorithm ROBUSTMEANEST that returns an estimate ji such that with probability at least 1 - 5,
j - ml 50() max E, log(L/8)
1- -t
log
log 1/6
We next present the algorithm in Algorithm 3.
We show that sampling with probability so that there are θ (1)) items S implies that |S] is roughly a (1 + O approximation to the total number of distinct elements. The statement well-known; we include the proof for completeness.
30

---

On Fine-Grained Distinct Element Estimation
Algorithm 3 Parameterized streaming algoritihm for distinct element estimation using robust statisties
Input: Accuracy parameter E (0, 1), number C' of coordinates that are greater than 1
Output: (1 + -aapproximationnn the number of distinct elements Fo
1: Let X E 100 Fol
2: Let 5 [n] be formed by sampling each item of [n] with probability p min (1, ToDe
3: + (
4: for E [B] do
5: Let Sy, sample each item of S with probability B
6: Let fo Fi (S6) be the total number of updates items in S.
7: end for
8: Z + B RoBuSTMEANEST
9: Return Z
Lemma D.3. With probability at least 0.99, we have
(1-2) Fo 1S| S (1+ 2)
Fo.
Proof. Let N be the set of distinct elements in the stream. Then we have
E ||S] =
Σ p=
IN)
iEN
and
N
22
E [|S?? S
Σ KEN
PS
|N
1
106
for p 2 10
Therefore, by Chebyshev's inequality, we have with probability at least 0.99.
1 |S| 1 p
< c
Fo-
We now justify the correctness of Algorithm 3.
Lemma D.4. If Fo(S) t and C 1. then Algorithm provides a (1 + e) appprximmaioo the number of distinct elements in the stream with probability least 0.98.
Proof. Let ff the frequency vector defined over the stream and let Z defined in Algorithm Let N₁ be the set of items with frequency in S and N>1 be the set of items with frequency larger than 1 in S. For any fixed E [B], let SoNN) denote the subset of N₁ sampled into S₁ and similarly, let Sz(N>1) denote the subset of N>1 sampled into Ss. The probability that [S&(Ns1) a binomial random variable with N, trials and B success rate. Hence, [N,, = B (INN l). [[N < 1/2 -N and moments of [Nx)N are finite. Therefore, by the guarantees of ROBUSTMEANEST Theorem D.2, we have that with high probability,
0 is (1 ) < & for sufficiently large = O (S). Moreover, the distribution of (Nx))
N₂
C
E Fo(S).
Z N s B
Fo(S)
4
Since Fo(S) 2 1 and C < 1 then | is (1 9 approximation Fo( Thus,
1 - Fo(S) < ε Fo(S).
31

---

On Fine-Grained Distinct Element Estimation
Finally by Lemma D.3, have with probability least 0.99,
(1 (1-4)
c Fo - P
Fo(S) - (1+ 4)= Fo.
so that with probability at least 0.98,
Z -I1lllo S =-
Next, we analyze the space complexity of Algorithm 3.
Lemma D.5. For a stream with length polynomially bounded in n, Algorithm uses ( logn) bits of space.
Proof. Note that Algorithm 3 maintains / = =0 ( buckets, each represented by counter using O (log n) bits of space for stream with length polynomially bounded in n.
Putting together the correctness of approximation and the space bounds, we have the following:
Theorem D.6. Given an accuracy parameter E (0, 1), parameter C' S 1 for the number of coordinates with frequency 45 more than 1, and number of distinct elements that is at least S ( there exists one-pass streaming algorithm that uses O log n) bits of space and provides (1 + appproxximtao the number of distinct elements in the stream with probability at least 0.98.
D.2. Subsampling
In this section, present two-pass streaming algorithm based on subsampling. We give an algorithm for when the number of coordinates with frequency greater than one is relatively "large" in Algorithm 4 and for the case where the number of coordinates with frequency greater than one is "small" in Algorithm 5.
Algorithm 4 Parameterized distinct element estimation over two-pass streams
Input: Accuracy parameter E (0, 1), number C' of coordinates that are greater than Output: (1+ e) appproximatonnn the number distinct elements, given two passes over the data
1: L + 0 0 4) J.B + C. polylog ("),
log
2: f [L] do
3: Form S; by sampling each item of [n] with probability 221-2
4: Run O nlogn) instances of COUNTŠKETCH on Se with B buckets
>First pass
5: end for
6: for each heavy-hitter E [n] reported by COUNTSKETCH on any S; do Track fo exactly
>Second pass
8: end for
9: for E E [L] do
M, =0
for j St do
12:
if ff 2 T then
13:
M, + M, + (f, 1)
14:
else if f, E
T --
then
15:
8 + max 0, - log 10
log " ))
Mr Mr + 229 (f) 1)
17:
end if
18: end for
19:
end for
20: Return F((S,) - EeE(L) Mr
32

---

On Fine-Grained Distinct Element Estimation
Lemma D.7. Let Z be the oulput of Algorithm 4. Then with probability al least 3o we have that
1 Fo()) - =Fo(S).
Proof. Let S be the data stream. For each i [n], let m, max(0, fi 1) that t, is the excess mass of fi- Let M- = Eie(n] m, so that (S) (i) M. Thus to achieve (1 + a)-aproxximation to (S))), it suffices to obtain an additive E Fo approximation to M.
Let level set i = {i E [m] 4 I consist of the coordinates i E [nx] with frequency at least T Similarly, for > 1, let level set r {i E [m] :
2- 1 ( consist of the coordinates E [v]] with frequency in the interval [ (-, Let
Mr = Eier, fs be the sum of the contributions of the items in level set rr. Finally, let I' be the set of all coordinates with value greater than 1.
For each i Mr. we have that i sampled with probability pt = 2 where
Br max
0,e -
log
10
log
71
Hence, we consider casework on whether L s log (10 (10(X2
yC
log / or whether <> log (10
VC
log )
Suppose L < log [10 yC log 2 that pt 1. Then i E St for any i T'g. Let G. denote the probability that i is not hashed by the r-th instance of COUNTSKETCH to a bucket containing any of the other items in I, so that we have Pr[E,] 2 2 since r|| I and we use B C polylog (#) buckets in each instance of COUNTSKETCH. Then let denote the probability that for all items E S there exist O (logn) instances of COUNTSKETCH such that is not hashed to a bucket containing any of the other items in T6 ( Se, so that have Pr [E] Pr [91 V G2 V ....]
poly(a)
Conditioning on Gr. the variance for the estimation of f. by the r-th instance COUNTSKETCH is at most 전े E Since fi oي 2 Cea log? then COUNTS reports fi heavy-hitter with probability 3. Therefore, have that with high probability, i is reported i Sg, we have that with high probability, Me Mg.
100
heavy-hitter by some instance of COUNTŠKETCIL, Hence by union bound over all
Next, we suppose l > log (10
[VC log nh so that 1 2
where
VC
n
Br max 0,e 1-8-log log
10
log
Then for any i E Te, we have i E Sz with probability pe- Let El denote the event that (o(e) I (10logn) Pe (o( so that Pr [&]] 2 Ton Again, let G, denote the event that i E Sz is not hashed by the r-th instance of COUNTSKETCH to a bucket containing any of the other items in I,, so that we have Pr [E,] 2 2nd since [I'] S C' ('and we use B = C. polylog (2) buckets each instance of COUNTSKETCIL Moreover, let &g denote the probability that for all items i E S I', there exist O (log n) instances of COUNTSKETCH such that not hashed to bucket containing any of the other items in nS.. pn] Conditioning on ε and &r, the variance for the estimation of fi
Then have Pr [82] Pr |91 V G2 v ... -] 2
by the r-th instance COUNTŠKETCH is at most 100 (10log Pr. Since Si 2 T 2 10 log then COUNTSKETCH
T
2 Therefore, we have
reports as heavy-hitter with probability at least
1 Pe
E
M
De f3 = M
JET2
Furthermore,
T
22.
E²
E
(M
< Σ
pt. P3
<
F2((),
P JET,
22d
rCT log (2)
y >log² (n)
for some large constant 7 >>> 1. Thus by Chebyshev's inequality, we have that with probability at least 1
100 log x
M
Me < L
Fo-
The result then follows from union bounding over all level sets T T1,..., . TL-
33

---

On Fine-Grained Distinct Element Estimation
To complete the guarantees of Algorithm 4, it remains analyze the space complexity.
Theorem D.8. Given a stream an accuracy parameter & E (0, 1), parameter 2 1. Fo(5) for the number of
coordinates with frequency more than and a number of distinct elements that is least Fo(S) = 2 (22), there exists
two-pass streaming algorithm that uses C- polylog (e) bits of space and provides a (1 -apprrxttiinni to the number of distinct elements the stream with probability at least 0.98.
Proof. The proof of correctness follows from Lemma D.7. The space complexity follows from the fact that we maintain B buckets in each of the O (log n) instances of COUNTSKETCH, for B = C polylog (+).
now show that for C> 1. any algorithm for (1 + -ppproxxxinn to distinct elements requires S2(C') bits of space. Recall that in and the goal is to determine whether the Hamming distance between X and Y is either at least /n or at most 2 vn.
problem, Alice is given binary vector E {0, 1)" and Bob given binary vector E [0,1]"
Theorem D.9. (Chakrabarti Regev, 2012) Any communication protocol that solves the Gap- Hammingg problem with probability least 3 requires Q(n) bits of communication.
Theorem D.10. For any frequency vector that has the number C C= (+) of coordinates with frequency more than 1, any one-pass streaming algorithm for (1 + e)-approximation of the number of distinct elements must use (min (2,,C) bits
of space.
Proof. Consider instance of Hap-HHmming that has (CC) coordinates, where C' 52 (4). . Note that for the purposes of the proof, it suffices to assume that C O ( Namely, let be the input vector Alice and let Y be the input vector Bob. Then Z X + Y has O (C') coordinates with frequency more than 1. Moreover, any (1 + s)-aprroximation
ZZ) will distinguish whether the Hamming distance between X and Y is at least n + /n less than //2 vn, since n= ( Therefore, such an algorithm can be used to solve Gap-Hamming on e(C) coordinates and by Theorem D.9 must use space (CC)
Algorithm 5 Parameterized distinct element estimation over two-pass streams
Input: Accuracy parameter (0, 1), stream with small number C' of coordinates with frequency larger than 1, i.e. C' < Output: + E) ()+ approximation to the number of distinct elements, given two passes over the data 1: L +- 0 (log 2). B +- polylog (=). T < 100
2 log" n
2: for E [L] do
3: Form S, by sampling each item of [n] with probability -
4: Run O (logn) instances of COUNTSKETCH on Se with B buckets
>First pass
5: end for
6: for each heavy-hitter E [n]] reported by COUNTSKETCHI any S; do
7: Track fi exactly
>Second pass
8: end for
9: for L [L] do
10:
Mr 0
11:
for E St do
12:
if f; 2 T then
13:
Mi Mn + (fz 1)
14:
else if fa E
T
3:251 then
15:
3 - max (0,e- log 10 log m)
16:
Mr Mr + 23 (Ji - 1)
17: end if
18:
end for
19:
end for
20:
Return F((S)) - ElELy Me
We now justify the correctness of Algorithm
34

---

On Fine-Grained Distinct Element Estimation
Lemma D.11. Let Z be the output of Algorithm 5 and suppose the number C of pairwise collisions is most 1. Then with probability at least 3. we have that
- Fo()) =Fo(S))
Proof. Let S be the data stream and for each i [n], let m, max(0, fi 1) so that t; is the excess mass of ft- Let M = Eietn) m, so that (S) (i) - M. To achieve a (1 + "approximation to (o)S), it suffices to obtain an additive e. Fo approximation to M.
2 comprise the coordinates i E [rx] with frequency at least T. Now for integer L E (1, L), we define level set re- {i E [n]
Let level set [1 = {i [n] : fi 2
2. ز to consist of the coordinates i E [r]] with frequency in the TT 2 (
interval 1 ) Let Mr - Eier, Ja be the sum of the contributions of the items in level set rg. Let I' be the set of all coordinates with value greater than 1.
For each coordinate E Me, is sampled with probability Pt 1 28, where
0,6 0--- - log (10
log 12 = ))
B. max
10
Therefore, we consider casework on whether 6 < log [ log =) or whether > log 10 log ))
We first consider the first case, where 1 5 log ( 10 log ") so that pt = 1. We have E St for any i E Te. Let Gr denote the probability that not hashed by the r-th instance of COUNTSKETCII to a bucket containing any of the other
E
items in r. so that we have Pr [E,] 2 since [| S C S 1 and we use B
polylog ( buckets in each instance of COUNT Then let & denote the probability that for all items i E S₁ n T2, there exist O (log n) instances of COUNTSKETCH such that i is not bashed to bucket containing any of the other items in I'2 n St, so that we have poly(n] Conditioning on G., the variance for the estimation of Si by the r-th instance E sr. Since fi - 2 10 log then COUNTSKETCU reports fi as a heavy-hitter with ē
Pr[E] = Pr (9i V G2 V ... 2
COUNTSKETCU is at most 1 100
probability 3. Thus, is reported as heavy-hitter by some instance of COUNTŠKETCH with high probability. It follows by
a union bound over all E Se that Mr- = Me high probability.
In the other case, we have > log (10 log ") & so that pe 2Pr where
10 log ") ))
Be max
(0,--10 log
so that Pr (r 2 1 Tonz Let 9, denote the event that E Se is not hashed by the r-th instance of COUNTŠKETCH to a bucket containing any of the other items in I, so that we have Pr [E,] 2 since [T| I C and we use = è polylog (#) buckets in each instance of COUNTSKETCH. Moreover, let &g denote the probability that for all items i S₃ I there exist O (log n) instances of COUNTSKETCH such that i not hashed to bucket containing any of the other items in T nS poly(n)- Conditioning on E1 and &r, the variance for the estimation of fi T 100 (10logn) Pe. Since f. 2 - 2 10 log then COUNTSKETCH reports fü as heavy-hitter with probability at least Hence,
For any E Te. we have i E St with probability pe. Define E, to denote the event that (St) <
Then have Pr [E2] Pr |9, V G2 V v...] 2
by the r-th instance COUNTSKETCH is at most
E
M
1
Σ JETe
pe fJ = Mc.
Pe
Moreover,
1 Σ
72
E
(Mi)
<
Pe 81 $ (Tel
22 2f
pi JET,
Now, we have
r T
35

---

On Fine-Grained Distinct Element Estimation
that for some large constant 7 1,
E (Me)
(S))))
yE²
log"
(2)
y log (2)
Thus by Chebyshev's inequality, we have that with probability at least 1
100 log
M Me S Fo-
The result then follows from union bounding over all L level sets T I TL.
We now give the full guarantees of Algorithm 5.
Theorem D.12. Given stream S, an accuracy parameter & E (0, 1), a parameter C S Fo( for the number of coordinates with frequency more than and a number of distinct elements that is least Fo(S) - Ω ( there exists two-pass streaming algorithm that uses 1 g polylog (+) bits of space and provides a (1 + -approximmain to the number of distinct elements in the stream with probability at least 0.98.
Proof. The proof of correctness follows from Lemma D.11. The space complexity follows from the fact that we maintain B buckets in each of the O (log n) instances of COUNT for B 1 polylog (?).
We now show that any algorithm for (1 + -approximmai to distinct elements requires Ω (+) bits space, even when <
Theorem D.13. For any frequency vector that has the number C = of coordinates with frequency more than 1. any one-pass streaming algorithm.for (1 + -)ppproxximation of the number of distinct elements must use Q2 (2) bits of space.
Proof. Consider instance of SetDisj that has =O (+) coordinates. Note that for the purposes of the proof, it suffices assume that C O (.)). Namely, let X be the input vector to Alice and let Y be the input vector to Bob. Then Z := X -Y has most single coordinate with frequency more than 1. Moreover, any + apprrooximtioonn Fo(Z) will distinguish whether the X and Y are disjoint, since we can also compute Fi (2). Therefore, such an algorithm can be used to solve DejDisj on θ (?) coordinates and must use space Q (2).
36


Reviews:
[{"review_id": "u0dHIqqWeL", "reviewer": "Reviewer_XJEv", "summary": "In this paper the problem of distinct element estimation is studied. More precisely, we are given an universe [n] and $\\alpha$ servers and each of the servers receives a subset of the universe. Now, the goal is to compute a $(1+\\epsilon)$-approximation of the number of distinct elements using minimal communication among the servers.\nThis problem is well-studied and worst case bounds exists.\nThese bounds, however, are  based on assumptions which do not hold in practice.\nThus, this problem is studied parameterized by the number of pairwise collisions.\nUsing this parameter the paper presents a protocol with a low number of bits for communication, breaking previous lower bounds if the parameter is small.\nAlso, matching lower bound under this parameter a presented.\nFinally, a proof-of-concept implementation is provided which shows the effectiveness of the new protocol.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback and insightful questions.\n\n> For the experiments...more data sets can be generated\n\nWe 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\n\n> l 87 c 1: please define zipifan distribution\n\nWe have added the formal definition of Zipfian distribution in the preliminiaries and provided a forward pointer at this location. \n\n> l 124-129 c1: please provide an explanation for this behavior\n\nWe 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!\n\n> l 237 c2: constant factor >> 4-approx\n\nWe have specified this in the algorithm.\n\n> l 670: what is P,Q?\n\n$P$ and $Q$ are the two distributions $\\mu_1$ and $\\mu_2$ -- we have unified the notation now. \n\n> l 678: I think this formal description of the problem should be part of the main body\n\nThanks 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. \n\n> 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)\n\nWe 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. \n\n> l 797L where does the factor 100 come from?\n\nThe 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.\n\n> l 866: this seems natural; but please provide the padding argument here\n\nWe have added a description of the padding argument to the corresponding location in the appendix.  \n\n> l 877: why ``Unfortunately''? I think this is a positive result\n\nThis 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. \n\n> l 974: please provide a reference for this lower bound\n\nThanks, we have added the reference to this lower bound, appearing in Jayram and Woodruff (2013). \n\n> appendix C.1 had some nice motivation; I think this should also be mentioned in the main body\n\nAlthough 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. \n\n> 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?\n\nOur 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. \n\nIn 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. \n\n> 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?\n\nIntuitively, 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. \n\n> 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.\n\nYes, 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$.", "claims_and_evidence": "I think all claims in the paper are convincing.", "methods_and_evaluation_criteria": "For the theory, I say yes.\n\nFor the experiments, I think the data set is quite small. I think without too much effort more data sets can be generated, for example by considering each batch of 1 million events individually. This then results in 40 times as many data sets.\nI don't think that this is a big issue since the main focus of the paper is theory and the experiments so far already show that the new approach is very good in practice.", "theoretical_claims": "Since I am not an expert in the field, I only checked some small proofs and tried to understand the ideas of the proof. I skipped most proofs in the appendix.", "experimental_designs_or_analyses": "Yes, I checked the experimental details. I am convinced by the result. \nI only think that more data should be used to obtain higher quality results (see Methods And Evaluation Criteria). However, I don't think that this would change the results drastically.", "relation_to_broader_scientific_literature": "The key idea is to use the parameter C of pairwise collisions. This is a new idea and this parameter is small in practice.\nFor the unparameterized setting the authors cite all relevant literature as far as I can tell.", "essential_references_not_discussed": "No, see Relation To Broader Scientific Literature", "other_strengths_and_weaknesses": "combining parameterized algorithmics and distinct element estimation is a natural idea and shows the future potential of this approach for other related problems", "other_comments_or_suggestions": "l 87 c 1: please define zipifan distribution\n\nl 124-129 c1: please provide an explanation for this behavior\n\nl 237 c2: constant factor >> 4-approx\n\nl 670: what is P,Q?\n\nl 678: I think this formal description of the problem should be part of the main body\n\nl 750: Here your arguments were to short for me to understand the proof as a non expert. Providing more details here would be very helpful for me. For example instead of ``using standard expectation and variance techniques'' please provide the precise arguments.\n(similar in l 770)\n\nl 797L where does the factor 100 come from?\n\nl 866: this seems natural; but please provide the padding argument here\n\nl 877: why ``Unfortunately''? I think this is a positive result\n\nl 974: please provide a reference for this lower bound\n\nappendix C.1 had some nice motivation; I think this should also be mentioned in the main body", "questions_for_authors": "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?\n\nQ2: 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?\n\nQ3: 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.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JKIVyAXInu", "reviewer": "Reviewer_iXZ8", "summary": "The paper studies distinct element estimation in a distributed setting, where $\\alpha$ servers each hold a subset of elements from $[n]$. The goal is to compute the total number of distinct elements approximately while minimizing communication cost.  \n\nFor a $(1 + \\epsilon)$-approximation, prior works establish tight bounds of $\\Theta(\\alpha / \\epsilon^2 + \\alpha \\log n)$, assuming a constant fraction of elements appear in a constant fraction of servers. \n\nThis paper explores a setting where most elements are not widely replicated across servers. Under the assumption that the number of pairwise collisions $C$ satisfies $C = \\beta \\cdot O(\\min (F_0(S), 1 / \\epsilon^2 ))$, where $F_0(S)$ denotes the number of distinct elements, the authors improve the upper bound to $O(\\alpha \\log n \\log \\log n + \\sqrt{\\beta} (\\log n) \\cdot \\min (F_0(S), 1/ \\epsilon^2))$, with further improvements when $C < F_0(S)$. The paper also establishes matching lower bounds.  \n\nAlgorithms 1 and 2 build on standard techniques, but their analysis leverages the newly introduced pairwise collision parameter.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback and the pertinent question regarding Algorithm 1.\n\n> 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.\n\n> 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.\n\nThis 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!\n\n> Line 124, $C=O(\\alpha)$? Maybe something is missing there.\n\nWe 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.", "claims_and_evidence": "Yes, the claims are supported by mathematical guarantees.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "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.  \n\nSince 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.", "experimental_designs_or_analyses": "Experiments contain validation of the theoretical setting.", "relation_to_broader_scientific_literature": "The paper falls into the category of exploiting data patterns to overcome existing theoretical bounds.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper utilizes the input pattern to improve the current bounds.", "other_comments_or_suggestions": "1. See Theoretical Claims.\n2. Line 124, $C = O(\\alpha)$? Maybe something is missing there.", "questions_for_authors": "See Theoretical Claims.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ZdqwibmqTA", "reviewer": "Reviewer_VuAd", "summary": "The submission provides a more detailed theoretical analysis of the Distributed Distinct Element Estimation problem and shows that under certain assumptions on the distribution of the data points across servers (in particular concerning the number of collisions), previous lower bounds can be overcome. The main contributions include a new theoretical algorithm/protocol with more refined guarantees and an experimental evaluation.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive assessment and thoughtful questions.\n\n> 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.\n\nThank 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.\n\n> 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)?\n\nOur 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.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I did not spot any issues with the theoretical claims.", "experimental_designs_or_analyses": "I did not spot any issues with the experimental design.", "relation_to_broader_scientific_literature": "There is a well-documented connection to previous work.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "The conceptual idea behind the submission is a good one: there are well-established lower bounds for Distributed Distinct Element Estimation, but these assume certain distributions and it is natural to ask whether the lower bounds can be circumvented when the distributions are closer to those that may occur in some real-world scenarios. The authors show that this is indeed the case. They also provide lower bounds which show that under the considered assumptions, their results are basically tight. The proofs are non-trivial, and overall the contributions are sufficient and in line with what I would expect from a primarily theoretical ICML paper. \n\nThe 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. The paper is also well-written and nicely discusses the implications / context of the obtained results.\n\n## Update after rebuttal\nI maintain my assessment and score.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "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)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "YeBFTio7RF", "reviewer": "Reviewer_GxnD", "summary": "This paper considers the distinct elements problem in a distributed setting. There are $\\alpha$ servers and a universe of $n$ elements, represented as a frequency vector $S$ over all elements in the universe. Each server has a subset $S_i$ of the items. The goal is for the server to send messages to a coordinator such that the number of non-zero entries of $S:=\\cup S_i$, denoted by $F_0(S)$ are estimated up to a multiplicative $(1\\pm \\varepsilon)$ factor.\n\nThe authors give a messaging protocol that, assuming an upper bound of $\\beta$ on the sum of overlaps $|S_i\\cap S_j|$ over all pairs, uses $O(\\alpha\\log n\\log\\log n + \\sqrt{\\beta} \\varepsilon^{-2}\\log n)$ bits, bypassing the $O(\\alpha(\\log n + \\varepsilon^{-2}))$ worst case lower bound. The authors also offer further improvements if the number if the number of pairwise collisions is promised to be less than $F_0(S)$. In addition, the authors show that in the regime where there results are interesting, that is in the regime where $\\beta$ is small compared to $\\alpha$, the dependency on $\\beta$ achieved by their algorithms is also necessary. Finally, the authors also showcase that their ideas can also be extended to other fields, most notably streaming algorithms where they achieve a multi-pass streaming algorithm with only $\\text{polylog}(\\varepsilon^{-1},\\log n)$ bits of space, as opposed to the polynomial dependencies on $\\varepsilon^{-1}$ that are typically necessary.\n\nThe algorithms use subsampling ideas to first obtain a coarse estimation of $F_0(S)$ and then likewise to refine the estimation to a the desired $(1\\pm \\varepsilon)$ factor.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback and constructive criticism.\n\n> 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\n\n> It also uses subsampling as opposed to sketching ideas for distinct elements.\n\nThank you for pointing out this reference. We have added a reference as an additional work that uses subsampling. \n\n> 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.\n\nWe 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. \n\nOn 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. \n\n> 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.\n\nWe 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.\n\nAdditionally, 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.", "claims_and_evidence": "-", "methods_and_evaluation_criteria": "-", "theoretical_claims": "The proofs in the main body are correct. I only skimmed the results in the supplementary material, but the proof of the first streaming algorithm is also correct.", "experimental_designs_or_analyses": "-", "relation_to_broader_scientific_literature": "The distinct elements problem is very well studied, but now in the classic sense effectively closed. Some research on this area is still active, but those results typically focus on more general problems.\n\nThe authors show that the worst case bound of $\\Theta(\\alpha (\\log n + \\varepsilon^{-2}))$ can be improved and that the assumption that they are making is, in some sense, necessary.", "essential_references_not_discussed": "The related work is reasonable, so missing the following reference did not affect my rating of the paper. \n\nMridul Nandi, N. V. Vinodchandran, Arijit Ghosh, Kuldeep S. Meel, Soumit Pal, Sourav Chakraborty:\nImproved Streaming Algorithm for the Klee's Measure Problem and Generalizations. APPROX/RANDOM 2024\n\nIt also uses subsampling as opposed to sketching ideas for distinct elements.", "other_strengths_and_weaknesses": "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.\n\nThe 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.\n\nI feel it is a borderline paper, which I rounded up to a weak accept.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: Reviewers generally appreciate the conceptual message of this paper, particularly the idea of leveraging dataset properties in practice to bypass worst-case lower bounds. While some noted that the algorithmic ideas and analysis lack significant novelty, they found them generally acceptable. Please consider to incorporate the following reviewer suggestions into the next version of the paper: (1) Remove Algorithm 1 to streamline the presentation. (2) (Optional) develop a method for learning the number of pairwise collisions to ensure that the worst-case bounds asymptotically align with the state-of-the-art across all parameter ranges.
Decision: Accept (poster)