Research map / Learning theory and algorithms / Combinatorial and search optimization
Topkapi: Parallel and Fast Sketches for Finding Top-K Frequent Elements
Ankush Mandal, He Jiang, Anshumali Shrivastava, Vivek Sarkar
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (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 |
|---|---|---|---|
| attach a size-1 Frequent summary (local heavy hitter) to each CMS counter, replacing the heap | Count-Min Sketch · top-K precision, 128GB | precision (%): 11.6 -> 95 | Improved |
| attach a size-1 Frequent summary to each CMS counter | Count-Min Sketch · top-K precision, 16GB | precision (%): 64.4 -> 96 | Improved |
| use Topkapi instead of Frequent algorithm | distributed top-K · precision, 16GB | precision (%): 87 -> 96 | Improved |
| use Topkapi instead of Frequent algorithm | distributed top-K · precision, 128GB | precision (%): 94 -> 95 | Improved |
| double CMS counters from 1024 to 2048 (ablation) | CMS · precision, 128GB | precision (%): 11.6 -> 49.66 | Improved |
| use Topkapi instead of Frequent algorithm | multi-threaded distributed execution · 16GB, 64 threads single node | speedup: 22x | Improved |
| reduce K from 100 to 50 (ablation) | Topkapi speedup over Frequent · 16GB | speedup over FA: 2.73x-3.01x | Improved |
| increase K from 100 to 200 (ablation) | Topkapi speedup over Frequent · 16GB | speedup over FA: 2.21x-2.36x | Hurt |
| two-pass CMS instead of single-pass CMS with heap (ablation) | CMS · 16GB | execution time: 0.97x | No clear effect |
Closest papers by meaning
- New Parallel and Streaming Algorithms for Directed Densest Subgraph (NeurIPS 2025 · similarity 0.82)
- Faster Streaming and Scalable Algorithms for Finding Directed Dense Subgraphs in Large Graphs (ICML 2024 · similarity 0.82)
- Fully-Scalable Massively Parallel Algorithm for k-center with Outliers (AAAI 2025 · similarity 0.82)
- ZETA: Leveraging $Z$-order Curves for Efficient Top-$k$ Attention (ICLR 2025 · similarity 0.81)
- LapSum - One Method to Differentiate Them All: Ranking, Sorting and Top-k Selection (ICML 2025 · similarity 0.81)
- MaxSketch: Robust Distinct Counting in Streams via Random Projections (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.
