Finding Hierarchical Heavy Hitters in Data Streams

Summary: Defines Hierarchical Heavy Hitters (HHH) in data streams: report nodes whose discounted descendant counts reach phi of the total, under a hierarchy. Presents deterministic and randomized, hierarchy-aware algorithms that outperform naive approaches, with experiments showing improved accuracy. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8997
Venue: VLDB
Year: 2003
Pagerank: 5.7580375e-05
Overall Rank: 5,016 | 65.11%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,629	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00011085267
3,660	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.8691367e-05
4,334	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.2798179e-05
6,362	SLEUTH: Single-publisher attack detection Using correlation Hunting	2008	VLDB	5.0953013e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
8,522	Differentially Private Hierarchical Heavy Hitters	2024	PODS	4.4937074e-05
8,697	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.4657888e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
472	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.00022346384
865	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00015808172
1,655	Gigascope: High Performance Network Monitoring with an SQL Interface	2002	SIGMOD	0.00010997332

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,068	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB	4.4034035e-05
6,799	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD	4.9232394e-05
10,983	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1945683e-05
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05
4,249	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.3245666e-05
11,449	Data Summarization with Hierarchical Taxonomy	2021	SIGMOD	4.1945683e-05
6,599	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9973567e-05
4,334	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.2798179e-05
8,522	Differentially Private Hierarchical Heavy Hitters	2024	PODS	4.4937074e-05
3,660	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.8691367e-05