Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing

Summary: Cuckoo Heavy Keeper (CHK) reverses the usual frequent/infrequent distinction to balance insertion and query costs in parallel heavy-hitter tracking. It delivers 1.7–5.7× higher throughput, orders-of-magnitude better accuracy, and near-linear scale-up under tight memory. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14137
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,910 | 25.15%
DOI: 10.14778/3746405.3746434

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Vinh Quang Ngo (Chalmers University of Technology; University of Gothenburg)
2. Marina Papatriantafilou (Chalmers University of Technology; University of Gothenburg)

BibTeX Citation

@article{ngo_vldb25,
        title = {{Cuckoo Heavy Keeper and the balancing act of maintaining heavy hitters in stream processing}},
        author = {Ngo, Vinh Quang and Papatriantafilou, Marina},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {9},
        pages = {3149--3161},
        doi = {10.14778/3746405.3746434},
        url = {https://doi.org/10.14778/3746405.3746434},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
451	Mergeable Summaries	2012	PODS	0.00018151445
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
885	Finding Frequent Items in Data Streams	2008	VLDB	0.00013419017
1,294	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011291308
3,044	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.820774e-05
4,460	Approximate Frequency Counts over Data Streams	2012	VLDB	6.689845e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,012	Parallel Index-based Stream Join on a Multicore CPU	2020	SIGMOD
2	3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
3	885	Finding Frequent Items in Data Streams	2008	VLDB
4	6,410	A Holistic View of Stream Partitioning Costs	2017	VLDB
5	6,766	Sharing-Aware Outlier Analytics over High-Volume Data Streams	2016	SIGMOD
6	11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD
7	8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD
8	4,782	Cuckoo Index: A Lightweight Secondary Index Structure	2020	VLDB
9	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
10	11,423	A Learned Cuckoo Filter for Approximate Membership Queries over Variable-sized Sliding Windows on Data Streams	2023	SIGMOD