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: h75015ae729760df3
Venue: SIGMOD
Year: 2004
Pagerank: 6.6322269e-05
Overall Rank: 4,353 | 70.83%
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,714	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.0553175e-05
6,267	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.8134046e-05
7,415	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.5160692e-05
8,014	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.3911362e-05
9,920	Relaxation in Text Search using Taxonomies	2008	VLDB	5.0983269e-05
12,745	Dissemination of Models over Time-Varying Data	2011	VLDB	4.9605343e-05
12,920	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	4.9605343e-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
124	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00030503973
404	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.00019034819
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
745	Dynamic Multidimensional Histograms	2002	SIGMOD	0.00014267268
860	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.00013382689
1,080	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012114187
2,444	The Generalized MDL Approach for Summarization	2002	VLDB	8.4450845e-05
5,179	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.225925e-05

Semantically Similar Papers

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