Pith. sign in

REVIEW 4 major objections 4 minor 89 references

On Fine-Grained Distinct Element Estimation

T0 review · 4 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Distributed distinct-element estimation is governed by pairwise collisions rather than by the worst-case $\alpha/\varepsilon^2$ bound, with matching upper and lower bounds in every collision regime.

desk verdict The collision parameterization is a good idea and the upper bounds are clean, but the small-collision lower bound rests on an unproved adaptation of [WZ12] and a false inequality in Lemma 4.4. read the letter →

arxiv 2506.22608 v1 pith:5P6D6MVE submitted 2025-06-27 cs.DS

Ilias Diakonikolas , Daniel M. Kane , Jasper C.H. Lee , Thanasis Pittas , David P. Woodruff , Samson Zhou This is my paper · ORCID
classification cs.DS MSC 68Q1168W20
keywords distinctelementsF0estimationcommunicationcomplexitypairwisecollisionsdistributedalgorithmsstreaminglowerboundsZipfiandata
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper argues that the communication cost of distributed distinct-element estimation is governed by the number $C$ of pairwise collisions -- instances where the same universe element appears on two or more servers -- rather than by the worst-case bound of $\Theta(\alpha \log n + \alpha/\varepsilon^2)$ bits. It presents a protocol whose communication scales roughly as $\sqrt{\beta}/\varepsilon^2$ when $C = \beta \cdot O(\min(F_0(S), 1/\varepsilon^2))$, breaking the previous lower bound whenever collisions are sparse. It backs this with lower bounds that match in all collision regimes, establishing $C$ as a tight complexity measure, and gives streaming analogues parameterized by the number of items with frequency greater than one. The upshot is an explanation of why distinct-counting problems that are hard in the worst case are often easy on real, skewed data such as network traffic.

What carries the argument

The load-bearing object is the pairwise collision count $C = \sum_i \binom{H_i}{2}$, where $H_i$ is the number of servers holding element $i$, together with the parameter $\beta$ defined by $C = \beta \cdot O(\min(F_0, 1/\varepsilon^2))$. The upper-bound protocol subsamples the universe until the coordinator sees $\Theta(1/\varepsilon^2)$ distinct items, and the collision bound controls through the root-mean-square/arithmetic-mean inequality how many items the servers must actually send. The small-collision lower bound is carried by a composed communication problem GapSet: the outer two-player GapAnd problem on $t = \Theta(1/\varepsilon^2)$ coordinates is combined with an inner multiplayer pairwise-disjointness problem on $n$ coordinates per block, so that each informative coordinate forces $\Omega(n)$ information and the whole instance forces $\Omega(nt)$ information.

What would settle it

Compute the squared Hellinger distance between the all-zeros input and a single-elementary-vector input under distribution $D_2$ with $k = \Theta(1)$ special servers: if it is $o(1)$, then Theorem 3.11's $\Omega(n)$ information bound for GUESS collapses and with it Theorem 1.4; alternatively, run the Theorem 1.1 protocol on a dataset with small $C$ but with no supplied collision bound and check whether communication jumps to the worst-case $\Theta(\alpha \log n + \alpha/\varepsilon^2)$ bits.

Watch

Extended reading notes

Core claim

The central claim is that the communication complexity of distributed $F_0$-estimation is the pairwise collision count $C$, not merely the accuracy $\varepsilon$ and the number of servers $\alpha$. Theorem 1.1 says that when $C = \beta \cdot O(\min(F_0(S), 1/\varepsilon^2))$, a $(1+\varepsilon)$-approximation can be computed in $O(\alpha \log n) + O(\min(F_0(S), 1/\varepsilon^2)) \sqrt{\beta} \log n$ bits; Theorem 1.3 says $\Omega(\sqrt{\beta} \min(F_0(S), 1/\varepsilon^2))$ bits are necessary when $C = \Omega(\beta F_0(S))$; and Theorem 1.4 says $\Omega(C/(\varepsilon^2 F_0(S)))$ bits are necessary when $C \in [\varepsilon F_0(S), F_0(S)]$ is promised. If these theorems are correct, the old $\Omega(\alpha/\varepsilon^2)$ lower bound applies only when collisions are abundant, and the number of pairwise collisions is the right fine-grained measure of the problem's difficulty.

Load-bearing premise

The improved results all rely on being handed a promised upper bound $C$ on the number of pairwise collisions before the protocol runs, and the small-collision lower bound additionally relies on a claimed but not derived Hellinger-distance calculation for the GUESS distribution where only $k = O(1)$ servers get the special coordinate; if either premise fails, that result loses its proof.

Editorial extensions

If this is right

  • For datasets with few pairwise collisions, the distributed protocol bypasses the $\Omega(\alpha/\varepsilon^2)$ lower bound; Zipfian data with exponent larger than 1 has $C = O(\alpha F_0)$, so communication reduces to $\tilde{O}(\alpha \log n)$ when $F_0$ is at least $1/\varepsilon^2$.
  • The matching lower bounds show the collision parameter is not an artifact: any protocol must pay $\Omega(\sqrt{\beta} \min(F_0, 1/\varepsilon^2))$ bits when collisions are abundant and $\Omega(C/(\varepsilon^2 F_0))$ bits when $C$ is small.
  • In the streaming model, two passes estimate the number of distinct elements in $O(C + 1/\varepsilon)$ bits and one pass in $O(C/\varepsilon)$ bits, with a matching $\Omega(C + 1/\varepsilon)$ lower bound, showing the $1/\varepsilon^2$ space barrier can be bypassed when few items repeat.
  • Because the lower bounds imply that estimating $C$ itself is hard when $C$ is small, the improved protocol cannot be obtained for free by first counting collisions; the improved guarantee requires $C$ as side information.
  • If $C < \varepsilon F_0(S)$, the servers can simply compute the total number of items $F_1(S)$ in $O(\alpha \log n)$ bits, giving a deterministic $(1+\varepsilon)$-approximation without sampling.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If pairwise collision count is the right parameter, the same lens likely transfers to other summary statistics -- support size, norm estimation, uniformity and closeness testing -- where worst-case hardness may vanish on skewed inputs; this is an extension the paper gestures at but does not develop.
  • The protocol's reliance on a promised upper bound $C$ invites a testable extension: estimate a loose collision bound from a small pilot sample or from historical data in the learning-augmented spirit, then run the promised protocol; the paper mentions this possibility but gives no analysis.
  • The one-pass streaming algorithm points to a concrete recipe -- CountSketch with $O(C/\varepsilon)$ buckets plus robust mean estimation on the bucket values -- that could be tested on non-Zipfian streams or extended to turnstile streams, where deletions make the collision count harder to bound.
  • The CAIDA experiment is a single proof-of-concept; a stronger empirical check of the paper's thesis would vary the skew of synthetic data and confirm that communication savings track $\sqrt{C}$ rather than $\alpha/\varepsilon^2$ across the full range.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper introduces a fine-grained parameterization of distributed distinct element estimation by the number C of pairwise collisions across servers. It claims upper bounds of the form O(alpha log n + sqrt(beta)/eps^2 log n) when C = beta * O(min(F0, 1/eps^2)), improved bounds when collisions are few, and matching lower bounds in all regimes, together with streaming algorithms parameterized by the number of items with frequency greater than 1 and an empirical evaluation on CAIDA trace data. The main technical novelty is a GapSet communication-game lower bound and a reduction from duplication detection, intended to establish the small-collision lower bound (Theorem 1.4).

Significance. If the results are correct, the paper would meaningfully refine the worst-case Theta(alpha/eps^2) communication bound for distributed distinct elements, identifying C as the right complexity measure and explaining why statistical problems with known worst-case hardness are often easy on skewed data. The collision parameterization is natural, and the paper includes runnable code and a concrete data-driven demonstration. However, the lower-bound machinery currently has unproved and quantitatively incorrect steps, and some upper-bound proofs conflate parameters after subsampling; the significance is therefore conditional on substantial repair.

major comments (4)
  1. [Section 3, Theorem 3.11 and Lemma 3.12] The GUESS lower bound is asserted rather than proved. The manuscript states that a protocol for the modified distribution D2, in which the special coordinate is assigned to only k=O(1) servers, has mutual information Omega(n), and justifies this only by saying that 'the mutual information is Omega(1) times the Hellinger distance between the all zeros vector and an elementary vector.' The required Hellinger-distance calculation for D2, the proof that this distance remains Omega(1) for k=O(1), and the direct-sum argument over the n coordinates are not given. Since Lemma 3.12 and Theorem 3.13 rest directly on Theorem 3.11, the Omega(nt) GapSet lower bound, and therefore Theorems 1.5 and 1.4, are unsupported as written.
  2. [Section 4, Lemmas 4.3 and 4.4] The reductions from duplication detection to GapAnd contain a quantitative error. Lemma 4.4 sets t=1/eps^2 and asserts 1/16*sqrt(t) >= eps*t/4, which is 1/(16*eps) >= 1/(4*eps) and is false. The correct requirement to resolve the GapAnd gap with a (1+eps)-approximation is eps*sqrt(t) <= 4c; with c=1/16 this is eps*sqrt(t) <= 1/4, so t=1/eps^2 fails since eps*sqrt(t)=1. Lemma 4.3 makes the same assertion with t=4C, which is equivalent to C <= 1/(64*eps^2), much stronger than the stated condition C < 4/eps^2. Additionally, Lemma 4.2 is false as stated: for Bin(t,1/4) and c=1/16, the central limit theorem gives Pr(|X-t/4|<c*sqrt(t)) approximately 0.11, which exceeds c=0.0625; the proof's Stirling simplification drops factors (3/4)^{1/2}(1/4)^{1/2}. The particular tail lower bound Pr(|D-t/4|>=c*sqrt(t))>=0.2 that is actually needed is true, but it is not established by the argument given. These issues are likely repairable, for example by choosing t=c'/eps^2 with a sufficiently small constant c', but as written the proofs of Lemmas 4.3 and 4.4 are invalid.
  3. [Section 2.2, proof of Theorem 1.1] The proof conflates the original collision parameter C with the number of pairwise collisions among the sampled items. After subsampling at rate 1/2^i, the sampled collision count is approximately 2^{-2i}C, not C itself, while the displayed decomposition C = sum_i (H_i choose 2) and the conclusion sum_i H_i = O(sqrt(beta*N)) require a bound of the form C_sampled = O(beta*N), where N is the number of sampled distinct items. No argument establishing this bound is supplied. The theorem may still be true, but the proof as written does not derive the advertised communication bound.
  4. [Section 1.1, Table 1 versus Theorem 1.4] For C = beta*F0 with beta<1 and F0>=1/eps^2, Table 1 lists a lower bound of Omega(alpha + beta*F0), while Theorem 1.4 states Omega(C/(eps^2*F0)) = Omega(beta/eps^2). Since eps^2*F0 >= 1 in this regime, the table is stronger by a factor eps^2*F0. No derivation of the stronger bound appears in the text; either a proof must be added or the table and the 'tight in all regimes' claim must be corrected.
minor comments (4)
  1. [Section 2.2, Algorithm 2] Line 3 of Algorithm 2 says 'i <- min(0,i0)', which is inconsistent with Algorithm 1's 'i <- max(0,i0)' and appears to be a typo; the proof of Theorem 1.2 also refers to X as a 4-approximation to F0(Si), whereas Algorithm 2 defines X as a 4-approximation to F0(S), so the intended statement is presumably that X/2^i approximates F0(Si).
  2. [Section 2.1, Corollaries 2.2 and 2.3] The phrase 'embed the same problem across beta players' is not spelled out for the full range beta in [1, alpha^2], especially when beta exceeds alpha; a brief construction or a comment on how the extra players are handled would clarify the proof of Theorem 1.3.
  3. [Section 6, experimental discussion] The text says the algorithm 'achiev[es] 70% error for eps=1' and then 'more than 95% error for eps=1/16'; this appears to describe accuracy rather than error and should be rephrased to avoid confusion.
  4. [Section 3, Lemma 3.2] Lemma 3.2 introduces a 'sufficiently small constant delta > 0' that is never used in the statement; clarifying the role of delta and the exact success-probability parameter would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: all three lower-bound regimes are imported from or derived via external information-complexity results, and the parameterized upper bounds are proved directly from the collision-count promise.

full rationale

The derivation chain is not circular. Theorem 1.1 is proved by subsampling and an RMS-AM bound: given C = beta * O(min(F0, 1/eps^2)) collisions, the protocol sends O(sqrt(beta) * min(F0, 1/eps^2)) items; the bound follows from the promise, not from the conclusion. Theorem 1.3 is explicitly a reparameterization of the external [WZ14] SUM-DISJ lower bound ('Theorem 1.3 follows immediately as a parameterization of a lower bound from [WZ14]'), which is legitimate reuse, not self-definition. The small-collision lower bound Theorem 1.4 reduces to GapSet, whose proof invokes Theorem 3.11 'by a similar argument to Theorem 5 in [WZ12]'; this is a self-citation (Woodruff overlaps) but the cited result is an independently proved external theorem whose assumptions do not include the present target, and the asserted modification to D2 is a missing proof step, not a circular one. The Zipfian fit in Section 6 is post-hoc data analysis and no fitted constant is used inside any theorem. The reviewer-flagged inequality in Lemma 4.4 (1/(16 sqrt(t)) >= eps*t/4 fails for t = 1/eps^2) and the unproved adaptation in Theorem 3.11 are correctness risks; they do not make any equation equivalent to its input by construction.

Assumptions & free parameters 4 free parameters · 9 assumptions · 0 invented entities

The theoretical claims rest on standard external lower bounds and data structure guarantees, all cited. The only fitted numbers are Zipfian parameters in the empirical section, and they do not feed into the proofs. No new physical or mathematical entities are postulated; GapSet and GUESS are proof constructs, not invented entities.

free parameters (4)
  • Zipfian exponent s (receiver IP distribution) = ~0.743
    Fitted in Section 6 to CAIDA receiver activity; used to support the claim that real data has few pairwise collisions. Not used in any theorem or algorithm.
  • Zipfian scale C (receiver IP distribution) = ~1404.68
    Fitted in Section 6 to CAIDA receiver activity; descriptive only, not load-bearing for the theoretical claims.
  • Zipfian exponent s (activity distribution) = ~0.344
    Fitted in Section 6 to CAIDA activity per sender; descriptive only, not load-bearing for the theoretical claims.
  • Zipfian scale C (activity distribution) = ~43.93
    Fitted in Section 6 to CAIDA activity per sender; descriptive only, not load-bearing for the theoretical claims.
assumptions (9)
  • standard math KNW10/Blasiok streaming distinct elements algorithm (Theorem 2.4)
    Used as the subroutine for the constant-factor approximation X in Algorithms 1 and 2.
  • standard math Information cost to communication complexity conversion and direct sum theorems from [BJKS04] (Fact 1.10, Theorem 1.19)
    Used in Section 3 to convert information lower bounds into communication lower bounds for GapSet.
  • standard math GapAnd information lower bound from [CKW12, PSW14, BGPW16] (Lemma 3.2)
    Serves as the outer lower bound in the GapSet composition proof.
  • standard math SUM-DISJ lower bound from [WZ14]
    Gives Theorem 1.3 via a direct reparameterization of the hard instance.
  • standard math Gap-Hamming lower bound from [CR12] (Theorem 5.9)
    Used for the streaming lower bounds in Section 5.
  • standard math CountSketch guarantees from [CCFC02] (Theorem 5.1)
    Used in the streaming algorithms to find heavy hitters.
  • standard math Robust mean estimation from [PBR19] (Theorem 5.2)
    Used in the one-pass streaming algorithm to estimate F0 from bucket counts.
  • standard math Stirling approximation (Fact 4.1)
    Used in Lemma 4.2; the proof's application appears to have an arithmetic error in the constant.
  • domain assumption The protocol is given an upper bound C on pairwise collisions as a promise
    Algorithm 2 and Theorem 1.2 require C as input; the paper notes that estimating C is itself hard and may need external side information.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On Fine-Grained Distinct Element Estimation." pith.science (2026). https://pith.science/paper/5P6D6MVE

@misc{pith2026250622608,
  author       = {Pith},
  title        = {Pith review of: On Fine-Grained Distinct Element Estimation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5P6D6MVE}},
  note         = {Machine review of arXiv:2506.22608}
}
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 $\mathcal{O}\left(\alpha\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.

Figures

Figures reproduced from arXiv: 2506.22608 by the authors.

Figure 1
Figure 1. Examples of YES and NO instances of the set disjointness problem for [PITH_FULL_IMAGE:figures/full_fig_p020_1.png] view at source ↗
Figure 2
Figure 2. Examples of input instances for GapSet problem for α = 2 players, t = 5 blocks, and n = 3 coordinates on each block. We first show the mutual information between a successful protocol for GapSet and a set of auxiliary variables. Lemma 3.10. Let Π be a protocol that solves GapSett,α,n,k with probability at least 0.99. Let {u (i)}i∈[α] be an input for GapSett,α,n,k, generated from vectors x, y drawn from GapAndt . Let… view at source ↗
Figure 3
Figure 3. Distributed protocol for duplication estimation [PITH_FULL_IMAGE:figures/full_fig_p030_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Histogram of unique senders per receiver in [PITH_FULL_IMAGE:figures/full_fig_p040_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

89 extracted references · 79 canonical work pages

  1. [1]

    Functional monitoring without monotonicity

    Chrisil Arackaparambil, Joshua Brody, and Amit Chakrabarti. Functional monitoring without monotonicity. In Automata, Languages and Programming, 36th International Colloquium, ICALP , Proceedings, Part I , pages 95--106, 2009

    2009

  2. [2]

    Mikl \' o s Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, and Samson Zhou. The white-box adversarial data stream model. In PODS '22: International Conference on Management of Data , pages 15--27, 2022

    2022

  3. [3]

    Detecting ddos attacks on isp networks

    Aditya Akella, Ashwin Bharambe, Mike Reiter, and Srinivasan Seshan. Detecting ddos attacks on isp networks. In Proceedings of the Workshop on Management and Processing of Data Streams , pages 1--2, 2003

    2003

  4. [4]

    Eliminating fuzzy duplicates in data warehouses

    Rohit Ananthakrishna, Surajit Chaudhuri, and Venkatesh Ganti. Eliminating fuzzy duplicates in data warehouses. In Proceedings of 28th International Conference on Very Large Data Bases, VLDB , pages 586--597, 2002

    2002

  5. [5]

    Canonne, and Himanshu Tyagi

    Jayadev Acharya, Cl \' e ment L. Canonne, and Himanshu Tyagi. Communication-constrained inference and the role of shared randomness. In Proceedings of the 36th International Conference on Machine Learning, ICML , USA , pages 30--39, 2019

    2019

  6. [6]

    Aggarwal

    Charu C. Aggarwal. Recommender Systems - The Textbook . Springer, 2016

    2016

  7. [7]

    Gibbons, Viswanath Poosala, and Sridhar Ramaswamy

    Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, and Sridhar Ramaswamy. The aqua approximate query answering system. In SIGMOD 1999, Proceedings ACM SIGMOD International Conference on Management of Data , pages 574--576, 1999

    1999

  8. [8]

    Zipf's law and the internet

    Lada A Adamic and Bernardo A Huberman. Zipf's law and the internet. Glottometrics , 3(1):143--150, 2002

    2002

Show all 89 references
  1. [9]

    Mayer, Kobbi Nissim, Benny Pinkas, and Michael K

    Vinod Anupam, Alain J. Mayer, Kobbi Nissim, Benny Pinkas, and Michael K. Reiter. On the security of pay-per-click and other web advertising schemes. Comput. Networks , 31(11-16):1091--1100, 1999

    1999

  2. [10]

    The space complexity of approximating the frequency moments

    Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. Comput. Syst. Sci. , 58(1):137--147, 1999

    1999

  3. [11]

    Data-driven algorithm design

    Maria - Florina Balcan. Data-driven algorithm design. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms , pages 626--645. Cambridge University Press, 2020

    2020

  4. [12]

    Dina Bitton and David J. DeWitt. Duplicate record elimination in large data files. ACM Trans. Database Syst. , 8(2):255--265, 1983

    1983

  5. [13]

    A tight bound for set disjointness in the message-passing model

    Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, and Vinod Vaikuntanathan. A tight bound for set disjointness in the message-passing model. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS , pages 668--677. IEEE Computer Society, 2013

    2013

  6. [14]

    Woodruff, and Samson Zhou

    Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, and Samson Zhou. Nearly optimal distinct elements and heavy hitters on sliding windows. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM , pages 7:1--7...

    2018

  7. [15]

    How to make your approximation algorithm private: A black-box differentially-private transformation for tunable approximation algorithms of functions with low sensitivity

    Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, and Samson Zhou. How to make your approximation algorithm private: A black-box differentially-private transformation for tunable approximation algorithms of functions with low sensitivity. In Approximation, Randomization, ...

    2023

  8. [16]

    Information lower bounds via self-reducibility

    Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. Information lower bounds via self-reducibility. Theory Comput. Syst. , 59(2):377--396, 2016

    2016

  9. [17]

    On the economics of offline password cracking

    Jeremiah Blocki, Benjamin Harsha, and Samson Zhou. On the economics of offline password cracking. In 2018 IEEE Symposium on Security and Privacy, SP , Proceedings , pages 853--871, 2018

    2018

  10. [18]

    Ziv Bar - Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. Counting distinct elements in a data stream. In Randomization and Approximation Techniques, 6th International Workshop, RANDOM , Proceedings , pages 1--10, 2002

    2002

  11. [19]

    Ziv Bar - Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. An information statistics approach to data stream and communication complexity. J. Comput. Syst. Sci. , 68(4):702--732, 2004

    2004

  12. [20]

    Optimal streaming and tracking distinct elements with high probability

    Jaroslaw Blasiok. Optimal streaming and tracking distinct elements with high probability. ACM Trans. Algorithms , 16(1):3:1--3:28, 2020

    2020

  13. [21]

    Burton H. Bloom. Space/time trade-offs in hash coding with allowable errors. Commun. ACM , 13(7):422--426, 1970

    1970

  14. [22]

    Mikhail Bilenko and Raymond J. Mooney. Adaptive duplicate detection using learnable string similarity measures. In Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 39--48, 2003

    2003

  15. [23]

    The caida ucsd anonymized internet traces

    CAIDA. The caida ucsd anonymized internet traces. https://www.caida.org/catalog/datasets/passive_dataset, 2016

    2016

  16. [24]

    Anomaly detection: A survey

    Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM Comput. Surv. , 41(3):15:1--15:58, 2009

    2009

  17. [25]

    Finding frequent items in data streams

    Moses Charikar, Kevin Chen, and Martin Farach-Colton. Finding frequent items in data streams. In International Colloquium on Automata, Languages, and Programming , pages 693--703. Springer, 2002

    2002

  18. [26]

    Robust identification of fuzzy duplicates

    Surajit Chaudhuri, Venkatesh Ganti, and Rajeev Motwani. Robust identification of fuzzy duplicates. In Proceedings of the 21st International Conference on Data Engineering, ICDE , pages 865--876, 2005

    2005

  19. [27]

    Chen, Piotr Indyk, and Tal Wagner

    Justin Y. Chen, Piotr Indyk, and Tal Wagner. Streaming algorithms for support-aware histograms. In International Conference on Machine Learning, ICML , pages 3184--3203, 2022

    2022

  20. [28]

    Near-optimal lower bounds on the multi-party communication complexity of set disjointness

    Amit Chakrabarti, Subhash Khot, and Xiaodong Sun. Near-optimal lower bounds on the multi-party communication complexity of set disjointness. In 18th Annual IEEE Conference on Computational Complexity (Complexity) , pages 107--117, 2003

    2003

  21. [29]

    Information complexity versus corruption and applications to orthogonality and gap-hamming

    Amit Chakrabarti, Ranganath Kondapally, and Zhenghui Wang. Information complexity versus corruption and applications to orthogonality and gap-hamming. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPR...

    2012

  22. [30]

    Muthukrishnan, and Ke Yi

    Graham Cormode, S. Muthukrishnan, and Ke Yi. Algorithms for distributed functional monitoring. ACM Trans. Algorithms , 7(2):21:1--21:20, 2011

    2011

  23. [31]

    Size-estimation framework with applications to transitive closure and reachability

    Edith Cohen. Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. , 55(3):441--453, 1997

    1997

  24. [32]

    Cohen and Jacob Richman

    William W. Cohen and Jacob Richman. 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 , pages 475--480, 2002

    2002

  25. [33]

    An optimal lower bound on the communication complexity of gap-hamming-distance

    Amit Chakrabarti and Oded Regev. An optimal lower bound on the communication complexity of gap-hamming-distance. SIAM J. Comput. , 41(5):1299--1317, 2012

    2012

  26. [34]

    Determinism vs

    Danny Dolev and Tom \' a s Feder. Determinism vs. nondeterminism in multiparty communication complexity. SIAM J. Comput. , 21(5):889--895, 1992

    1992

  27. [35]

    Loglog counting of large cardinalities (extended abstract)

    Marianne Durand and Philippe Flajolet. Loglog counting of large cardinalities (extended abstract). In Algorithms - ESA 2003, 11th Annual European Symposium, Proceedings , pages 605--617, 2003

    2003

  28. [36]

    Collision-based testers are optimal for uniformity and closeness

    Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price. Collision-based testers are optimal for uniformity and closeness. Chic. J. Theor. Comput. Sci. , 2019

    2019

  29. [37]

    Kane, and Alistair Stewart

    Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart. Sharp bounds for generalized uniformity testing. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS , pages 6204--6213, 2018

    2018

  30. [38]

    Bitmap algorithms for counting active flows on high speed links

    Cristian Estan, George Varghese, and Mike Fisk. Bitmap algorithms for counting active flows on high speed links. In Proceedings of the 3rd ACM SIGCOMM conference on Internet measurement , pages 153--166, 2003

    2003

  31. [39]

    Nigel Martin

    Philippe Flajolet and G. Nigel Martin. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. , 31(2):182--209, 1985

    1985

  32. [40]

    Distributed uniformity testing

    Orr Fischer, Uri Meir, and Rotem Oshman. Distributed uniformity testing. In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC , pages 455--464, 2018

    2018

  33. [41]

    A theory for record linkage

    Ivan P Fellegi and Alan B Sunter. A theory for record linkage. Journal of the American Statistical Association , 64(328):1183--1210, 1969

    1969

  34. [42]

    Finkelstein, Mario Schkolnick, and Paolo Tiberio

    Sheldon J. Finkelstein, Mario Schkolnick, and Paolo Tiberio. Physical database design for relational databases. ACM Trans. Database Syst. , 13(1):91--128, 1988

    1988

  35. [43]

    Zipf's law for cities: an explanation

    Xavier Gabaix. Zipf's law for cities: an explanation. The Quarterly journal of economics , 114(3):739--767, 1999

    1999

  36. [44]

    Phillip B. Gibbons. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In VLDB , Proceedings of 27th International Conference on Very Large Data Bases , pages 541--550, 2001

    2001

  37. [45]

    Woodruff, Huacheng Yu, and Samson Zhou

    Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, and Samson Zhou. A strong separation for adversarially robust _0 estimation for linear sketches. In 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 2318--2343, 2024

    2024

  38. [46]

    Finding duplicates in a data stream

    Parikshit Gopalan and Jaikumar Radhakrishnan. Finding duplicates in a data stream. In Claire Mathieu, editor, Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 402--411, 2009

    2009

  39. [47]

    Gonzalez, Reynold S

    Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. Graphx: Graph processing in a distributed dataflow framework. In 11th USENIX Symposium on Operating Systems Design and Implementation, OSDI , pages 599--613. USENIX Association, 2014

    2014

  40. [48]

    Learning-based frequency estimation algorithms

    Chen - Yu Hsu, Piotr Indyk, Dina Katabi, and Ali Vakilian. Learning-based frequency estimation algorithms. In 7th International Conference on Learning Representations, ICLR . OpenReview.net, 2019

    2019

  41. [49]

    Real-world data is dirty: Data cleansing and the merge/purge problem

    Mauricio A Hern \'a ndez and Salvatore J Stolfo. Real-world data is dirty: Data cleansing and the merge/purge problem. Data mining and knowledge discovery , 2:9--37, 1998

    1998

  42. [50]

    The randomized communication complexity of set disjointness

    Johan H stad and Avi Wigderson. The randomized communication complexity of set disjointness. Theory Comput. , 3(1):211--219, 2007

    2007

  43. [51]

    New observations on zipf's law in passwords

    Zhenduo Hou and Ding Wang. New observations on zipf's law in passwords. IEEE Trans. Inf. Forensics Secur. , 18:517--532, 2023

    2023

  44. [52]

    Lang, Zohar S

    Nikita Ivkin, Edo Liberty, Kevin J. Lang, Zohar S. Karnin, and Vladimir Braverman. Streaming quantiles algorithms with small space and update time. Sensors , 22(24):9612, 2022

    2022

  45. [53]

    Woodruff

    Piotr Indyk and David P. Woodruff. Optimal approximations of the frequency moments of data streams. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing , pages 202--208, 2005

    2005

  46. [54]

    Palak Jain, Iden Kalemaj, Sofya Raskhodnikova, Satchit Sivakumar, and Adam D. Smith. Counting distinct elements in the turnstile model with differential privacy under continual observation. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural In...

    2023

  47. [55]

    Tight bounds for lp samplers, finding duplicates in streams, and related problems

    Hossein Jowhari, Mert Saglam, and G \' a bor Tardos. 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 , pages 49--58, 2011

    2011

  48. [56]

    T. S. Jayram and David P. Woodruff. Optimal bounds for johnson-lindenstrauss transforms and streaming problems with subconstant error. ACM Trans. Algorithms , 9(3):26:1--26:17, 2013

    2013

  49. [57]

    Record Linkage Techniques, 1985: Proceedings of the Workshop on Exact Matching Methodologies , volume 1299

    Beth Kilss and Wendy Alvey. Record Linkage Techniques, 1985: Proceedings of the Workshop on Exact Matching Methodologies , volume 1299. Department of the Treasury, Internal Revenue Service, Statistics of Income …, 1986

    1985

  50. [58]

    Bell, and Chris Volinsky

    Yehuda Koren, Robert M. Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer , 42(8):30--37, 2009

    2009

  51. [59]

    Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins

    Jon M. Kleinberg, Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. The web as a graph: Measurements, models, and methods. In Computing and Combinatorics, 5th Annual International Conference, COCOON , Proceedings , pages 1--17, 1999

    1999

  52. [60]

    Kane, Jelani Nelson, and David P

    Daniel M. Kane, Jelani Nelson, and David P. Woodruff. An optimal algorithm for the distinct elements problem. In Proceedings of the Twenty-Ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS , pages 41--52, 2010

    2010

  53. [61]

    Woodruff

    Honghao Lin, Tian Luo, and David P. Woodruff. Learning augmented binary search trees. In International Conference on Machine Learning, ICML , pages 13431--13440, 2022

    2022

  54. [62]

    Memory-efficient performance monitoring on programmable switches with lean algorithms

    Zaoxing Liu, Samson Zhou, Ori Rottenstreich, Vladimir Braverman, and Jennifer Rexford. Memory-efficient performance monitoring on programmable switches with lean algorithms. In 1st Symposium on Algorithmic Principles of Computer Systems, APOCS , pages 31--44, 2020

    2020

  55. [63]

    Duplicate detection in click streams

    Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. Duplicate detection in click streams. In Proceedings of the 14th international conference on World Wide Web, WWW , pages 12--21, 2005

    2005

  56. [64]

    Austern, Aart J

    Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski. Pregel: a system for large-scale graph processing. In Proceedings of the ACM SIGMOD International Conference on Management of Data, SIGMOD , pages 135--146, 2010

    2010

  57. [65]

    Monge and Charles Elkan

    Alvaro E. Monge and Charles Elkan. An efficient domain-independent algorithm for detecting approximately duplicate database records. In Workshop on Research Issues on Data Mining and Knowledge Discovery, DMKD 1997 in cooperation with ACM SIGMOD , 1997

    1997

  58. [66]

    A brief history of generative models for power law and lognormal distributions

    Michael Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Math. , 1(2):226--251, 2003

    2003

  59. [67]

    A model for learned bloom filters and optimizing by sandwiching

    Michael Mitzenmacher. A model for learned bloom filters and optimizing by sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems, NeurIPS , pages 462--471, 2018

    2018

  60. [68]

    Approximate frequency counts over data streams

    Gurmeet Singh Manku and Rajeev Motwani. Approximate frequency counts over data streams. In Proceedings of 28th International Conference on Very Large Data Bases, VLDB , pages 346--357, 2002

    2002

  61. [69]

    Can distributed uniformity testing be local? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC , pages 228--237, 2019

    Uri Meir, Dor Minzer, and Rotem Oshman. Can distributed uniformity testing be local? In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC , pages 228--237, 2019

    2019

  62. [70]

    Communication-efficient learning of deep networks from decentralized data

    Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Ag \" u era y Arcas. Communication-efficient learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, AISTATS , pages ...

    2017

  63. [71]

    Muthukrishnan

    S. Muthukrishnan. Data streams: Algorithms and applications. Found. Trends Theor. Comput. Sci. , 1(2), 2005

    2005

  64. [72]

    Algorithms with predictions

    Michael Mitzenmacher and Sergei Vassilvitskii. Algorithms with predictions. In Tim Roughgarden, editor, Beyond the Worst-Case Analysis of Algorithms , pages 646--662. Cambridge University Press, 2020

    2020

  65. [73]

    Multi-dimensional clustering: A new data layout scheme in DB2

    Sriram Padmanabhan, Bishwaranjan Bhattacharjee, Timothy Malkemus, Leslie Cranston, and Matthew Huras. Multi-dimensional clustering: A new data layout scheme in DB2 . In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data , pages 637--641. ACM , 2003

    2003

  66. [74]

    A unified approach to robust mean estimation

    Adarsh Prasad, Sivaraman Balakrishnan, and Pradeep Ravikumar. A unified approach to robust mean estimation. CoRR , abs/1907.00927, 2019

    1907 arXiv

  67. [75]

    The connectivity and fault-tolerance of the internet topology, 2001

    Christopher R Palmer, Georgos Siganos, Michalis Faloutsos, Christos Faloutsos, and Phillip B Gibbons. The connectivity and fault-tolerance of the internet topology, 2001

    2001

  68. [76]

    Woodruff

    Rasmus Pagh, Morten St \" o ckel, and David P. Woodruff. Is min-wise hashing optimal for summarizing set intersection? In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS , pages 109--120, 2014

    2014

  69. [77]

    Insights from engineering sketches for production and using sketches at scale, 2023

    Lee Rhodes. Insights from engineering sketches for production and using sketches at scale, 2023

    2023

  70. [78]

    Grouplens: An open architecture for collaborative filtering of netnews

    Paul Resnick, Neophytos Iacovou, Mitesh Suchak, Peter Bergstrom, and John Riedl. Grouplens: An open architecture for collaborative filtering of netnews. In CSCW '94, Proceedings of the Conference on Computer Supported Cooperative Work , pages 175--186. ACM , 1994

    1994

  71. [79]

    Sofya Raskhodnikova, Dana Ron, Amir Shpilka, and Adam D. Smith. Strong lower bounds for approximating distribution support size and the distinct elements problem. SIAM J. Comput. , 39(3):813--842, 2009

    2009

  72. [80]

    Interactive deduplication using active learning

    Sunita Sarawagi and Anuradha Bhamidipaty. Interactive deduplication using active learning. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 269--278, 2002

    2002

  73. [81]

    Naughton, and Karthikeyan Ramasamy

    Amit Shukla, Prasad Deshpande, Jeffrey F. Naughton, and Karthikeyan Ramasamy. Storage estimation for multidimensional aggregates in the presence of hierarchies. In VLDB'96, Proceedings of 22th International Conference on Very Large Data Bases , pages 522--531, 1996

    1996

  74. [82]

    Finding a duplicate and a missing item in a stream

    Jun Tarui. Finding a duplicate and a missing item in a stream. In Theory and Applications of Models of Computation, 4th International Conference, TAMC , Proceedings , pages 128--135, 2007

    2007

  75. [83]

    Knoblock, and Steven Minton

    Sheila Tejada, Craig A. Knoblock, and Steven Minton. Learning domain-independent string transformation weights for high accuracy object identification. In Proceedings of the Eighth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining , pages 350--359, 2002

    2002

  76. [84]

    Zipf's law in passwords

    Ding Wang, Haibo Cheng, Ping Wang, Xinyi Huang, and Gaopeng Jian. Zipf's law in passwords. IEEE Trans. Inf. Forensics Secur. , 12(11):2776--2791, 2017

    2017

  77. [85]

    On the implications of zipf's law in passwords

    Ding Wang and Ping Wang. 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, pages 111--131. Springer, 2016

    2016

  78. [86]

    Woodruff and Qin Zhang

    David P. Woodruff and Qin Zhang. Tight bounds for distributed functional monitoring. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC , pages 941--960, 2012

    2012

  79. [87]

    Woodruff and Qin Zhang

    David P. Woodruff and Qin Zhang. An optimal lower bound for distinct elements in the message passing model. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA , pages 718--733, 2014

    2014

  80. [88]

    Woodruff and Samson Zhou

    David P. Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. In 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS , pages 1183--1196, 2021

    2021

  81. [89]

    The psycho-biology of language: An introduction to dynamic philology

    George Kingsley Zipf. The psycho-biology of language: An introduction to dynamic philology . Routledge, 2013

    2013

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.