Research map / Learning theory and algorithms / Sample complexity
On Fine-Grained Distinct Element Estimation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Parameterizes distributed distinct element estimation by the number of pairwise collisions C and gives protocols and matching lower bounds showing C is a tight complexity measure, plus streaming results parameterized by items with frequency above 1.
Problem
Distributed (1+ε)-approximation of the number of distinct elements across α servers; prior worst-case bounds Θ(α log n + α/ε²) assume hard instances where many coordinates appear on many servers, which may be unrealistic (e.g., Zipfian data).
Approach
Parameterize communication complexity by the number C of pairwise collisions (same element on multiple servers). Subsampling-based protocol communicates roughly sqrt(β) items per level when C = β·F0, and a separate protocol estimates excess mass when C is small; matching lower bounds are obtained via a GapSet composition and a distributed duplication detection reduction.
Key results
- Protocol communicates Õ(α log n + sqrt(β)/ε² log n) bits when C = β·Θ(min(F0, 1/ε²)), breaking the worst-case Ω(α/ε²) lower bound when collisions are few.
- Matching lower bounds Ω(α + sqrt(β)/ε²) for large collision counts and Ω(C/(ε²·F0)) for small collision counts are established.
- On the CAIDA dataset the algorithm outperforms worst-case bounds by several orders of magnitude, per the authors.
Surprising findings
- Estimating the number of collisions C itself to small communication is impossible in general, via the duplication detection lower bound.
Experimental setup
Datasets: CAIDA traffic dataset
Benchmarks: CAIDA
Metrics: communication cost approximation accuracy
Baselines: worst-case Θ(α log n + α/ε²) protocol subsampling-based F0 streaming protocol
Builds on: Gap-Hamming SUM-DISJ lower bound CountSketch
Closest papers by meaning
- Differentially Private Space-Efficient Algorithms for Counting Distinct Elements in the Turnstile Model (ICML 2025 · similarity 0.86)
- Lightweight Protocols for Distributed Private Quantile Estimation (ICML 2025 · similarity 0.81)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (NeurIPS 2026 · similarity 0.81)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.81)
- Private Continual Counting of Unbounded Streams (NeurIPS 2025 · similarity 0.80)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.