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.6469144e-05
Overall Rank: 4,348 | 70.77%
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,708	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS	7.0812099e-05
6,252	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.8354449e-05
7,992	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.4115836e-05
8,170	Together is Better: Heavy Hitters Quantile Estimation	2023	SIGMOD	5.3844369e-05
12,696	Dissemination of Models over Time-Varying Data	2011	VLDB	4.9793485e-05
12,870	Relaxation in Text Search using Taxonomies	2008	VLDB	4.9793485e-05
12,872	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	4.9793485e-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.00030600691
403	Bottom-Up Computation of Sparse and Iceberg CUBEs	1999	SIGMOD	0.0001910396
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
742	Dynamic Multidimensional Histograms	2002	SIGMOD	0.0001431602
858	What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically	2003	PODS	0.000134266
1,077	Multi-dimensional Selectivity Estimation Using Compressed Histogram Information	1999	SIGMOD	0.00012154948
2,434	The Generalized MDL Approach for Summarization	2002	VLDB	8.4746361e-05
5,157	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.2494766e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,874	Efficient Computation of Iceberg Cubes with Complex Measures	2001	SIGMOD
2	700	Explaining differences in multidimensional aggregates	1999	VLDB
3	742	Dynamic Multidimensional Histograms	2002	SIGMOD
4	4,798	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,004	Fast Algorithms For Hierarchical Range Histogram Construction	2002	PODS
7	866	Approximating Multi-Dimensional Aggregate Range Queries Over Real Attributes	2000	SIGMOD
8	4,529	What can Hierarchies do for Data Warehouses?	1999	VLDB
9	3,708	Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams	2005	PODS
10	5,157	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB