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: 8998
Venue: VLDB
Year: 2003
Pagerank: 5.635103e-05
Overall Rank: 5,188 | 63.95%
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,744	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010694459
3,701	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.825442e-05
4,463	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.1563782e-05
6,600	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9925547e-05
8,520	Differentially Private Hierarchical Heavy Hitters	2024	PODS	4.4893996e-05
8,695	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	4.461508e-05
12,397	SLEUTH: Single-publisher attack detection Using correlation Hunting	2008	VLDB	4.1905499e-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
475	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.00022238407
874	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001568356
1,671	Gigascope: High Performance Network Monitoring with an SQL Interface	2002	SIGMOD	0.00010944194

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
9,067	A Framework for Projected Clustering of High Dimensional Data Streams	2004	VLDB	4.3991821e-05
6,710	Incremental and Effective Data Summarization for Dynamic Hierarchical Clustering	2004	SIGMOD	4.9485574e-05
10,986	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD	4.1905499e-05
6,415	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.064828e-05
4,246	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.318484e-05
11,452	Data Summarization with Hierarchical Taxonomy	2021	SIGMOD	4.1905499e-05
6,600	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	4.9925547e-05
4,463	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.1563782e-05
8,520	Differentially Private Hierarchical Heavy Hitters	2024	PODS	4.4893996e-05
3,701	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	6.825442e-05