Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data

Summary: Extends HHHs to multi-dimensional hierarchies; analyzes overlap and split propagation across child-to-parent aggregation. Offline exact HHHs; online one-pass with provable accuracy uses diamond lattice to keep a fixed per-node stats, near-offline results. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3577
Venue: SIGMOD
Year: 2004
Pagerank: 6.7994155e-05
Overall Rank: 4,258 | 70.79%
DOI: 10.1145/1007568.1007588

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (Rutgers University)
2. S. Muthukrishnan (Rutgers University)
3. Flip Korn (AT&T)
4. Divesh Srivastava (AT&T)

BibTeX Citation

@inproceedings{cormode_sigmod04,
        title = {{Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data}},
        author = {Cormode, Graham and Muthukrishnan, S. and Korn, Flip and Srivastava, Divesh},
        series = {{SIGMOD} '04},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1007568.1007588},
        url = {https://dl.acm.org/doi/10.1145/1007568.1007588},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.2428869e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05
7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.5357919e-05
8,005	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5080221e-05
12,405	Dissemination of Models over Time-Varying Data	2011	VLDB	5.093636e-05
12,580	Relaxation in Text Search using Taxonomies	2008	VLDB	5.093636e-05
12,582	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
393	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001934104
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
723	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014620977
838	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.0001370404
1,053	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012401532
2,382	The Generalized MDL Approach for Summarization	2002	VLDB	8.6603462e-05
5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.3915389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,825	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD
2	700	Explaining differences in multidimensional aggregates	1999	VLDB
3	723	Dynamic Multidimensional Histograms	2002	SIGMOD
4	4,723	Aggregation Algorithms for Very Large Compressed Data Warehouses	1999	VLDB
5	213	Approximate Computation of Multidimensional Aggregates of Sparse Data Using Wavelets	1999	SIGMOD
6	4,889	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
7	850	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
8	4,427	What can Hierarchies do for Data Warehouses?	1999	VLDB
9	3,628	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
10	5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB