AI Paper Atlas

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

NeurIPS 2018 · Learning theory and algorithms › Combinatorial and search optimization · approach: Globally optimal geometric optimization · 10 citations (OpenAlex)

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 changedWhereMeasuredEffect
attach a size-1 Frequent summary (local heavy hitter) to each CMS counter, replacing the heapCount-Min Sketch · top-K precision, 128GBprecision (%): 11.6 -> 95Improved
attach a size-1 Frequent summary to each CMS counterCount-Min Sketch · top-K precision, 16GBprecision (%): 64.4 -> 96Improved
use Topkapi instead of Frequent algorithmdistributed top-K · precision, 16GBprecision (%): 87 -> 96Improved
use Topkapi instead of Frequent algorithmdistributed top-K · precision, 128GBprecision (%): 94 -> 95Improved
double CMS counters from 1024 to 2048 (ablation)CMS · precision, 128GBprecision (%): 11.6 -> 49.66Improved
use Topkapi instead of Frequent algorithmmulti-threaded distributed execution · 16GB, 64 threads single nodespeedup: 22xImproved
reduce K from 100 to 50 (ablation)Topkapi speedup over Frequent · 16GBspeedup over FA: 2.73x-3.01xImproved
increase K from 100 to 200 (ablation)Topkapi speedup over Frequent · 16GBspeedup over FA: 2.21x-2.36xHurt
two-pass CMS instead of single-pass CMS with heap (ablation)CMS · 16GBexecution time: 0.97xNo clear effect

Closest papers by meaning

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.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy