Research map / Learning theory and algorithms / Sample complexity
CountSketches, Feature Hashing and the Median of Three
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the median of 3 rows instead of 1 (ablation) | CountSketch frequency estimation · Kosarak | variance: 1.25 \times 10^{-5} -> 1.42 \times 10^{-7} | Helped |
| Use the median of 3 rows instead of 1 (ablation) | CountSketch frequency estimation · Sentiment140 | variance: 5.94 \times 10^{-6} -> 2.13 \times 10^{-7} | Helped |
| Use the median of 3 rows instead of 1 (ablation) | CountSketch frequency estimation · Zipfian α=0.8 | variance: 9.56 \times 10^{-6} -> 2.09 \times 10^{-7} | Helped |
| Use the median of 3 rows instead of 1 (ablation) | CountSketch frequency estimation · Zipfian α=1.2 | variance: 6.94 \times 10^{-5} -> 3.99 \times 10^{-7} | Helped |
| Use the median of 3 rows rather than a single row (ablation) | CountSketch frequency estimation · General vectors, for sufficiently large s | variance: 3 \|v\|_1^2/s^2 versus \|v\|_1^2/s | Helped |
| Use the median of 3 rows rather than a single row (ablation) | CountSketch inner product estimation · General vector pairs, for sufficiently large s | variance: 3 \|v\|_1^2\|w\|_1^2/s^2 versus \|v\|_1^2\|w\|_1^2/s | Helped |
Closest papers by meaning
- Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs (AAAI 2023 · similarity 0.87)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (NeurIPS 2026 · similarity 0.86)
- Fully Understanding The Hashing Trick (NeurIPS 2018 · similarity 0.85)
- C-MinHash: Improving Minwise Hashing with Circulant Permutation (ICML 2022 · similarity 0.84)
- Simple and Optimal Sublinear Algorithms for Mean Estimation (NeurIPS 2025 · similarity 0.81)
- Learning-Augmented Frequent Directions (ICLR 2025 · similarity 0.81)
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.