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: h69c7f6510b83ff18
Venue: VLDB
Year: 2025
Pagerank: 4.9793485e-05
Overall Rank: 11,304 | 24.00%
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
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
456	Mergeable Summaries	2012	PODS	0.0001791284
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
909	Finding Frequent Items in Data Streams	2008	VLDB	0.00013125647
1,319	Augmented Sketch: Faster and More Accurate Stream Processing	2016	SIGMOD	0.00011045888
3,094	Holistic UDAFs at Streaming Speeds	2004	SIGMOD	7.6533343e-05
4,550	Approximate Frequency Counts over Data Streams	2012	VLDB	6.5402546e-05

Semantically Similar Papers

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