Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams

Summary: Shows deterministic single-pass phi-HHHs in d-dimensional hierarchies require Omega(1/phi^(d+1)) space, explaining why prior O((1/phi) log(phi n)) schemes yield false positives. Provides a matching O(1/phi^(d+1)) algorithm that reports phi-HHHs without false positives. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1366
Venue: PODS
Year: 2005
Pagerank: 7.2428869e-05
Overall Rank: 3,628 | 75.11%
DOI: 10.1145/1065167.1065211

Incoming Non-self Citations Over Time

Authors

1. John Hershberger (Mentor Graphics Corporation)
2. Nisheeth Shrivastava (University of California Santa Barbara)
3. Subhash Suri (University of California Santa Barbara)
4. Csaba D. Tóth (Massachusetts Institute of Technology)

BibTeX Citation

@inproceedings{hershberger_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065211},
        doi = {10.1145/1065167.1065211},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Hershberger, John and Shrivastava, Nisheeth and Suri, Subhash and Tóth, Csaba D.},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS	0.00010240222
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.8746921e-05
7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS	5.5357919e-05
8,603	Stream Frequency over Interval Queries	2019	VLDB	5.4041343e-05
11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
4,258	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.7994155e-05
5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.3915389e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	11,196	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
2	654	Storage Estimation for Multidimensional Aggregates in the Presence of Hierarchies	1996	VLDB
3	9,537	Finding Heavy-Hitters with Optimal State Changes	2026	PODS
4	11,638	Frequent Elements with Witnesses in Data Streams	2021	PODS
5	11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD
6	1,600	Space-optimal Heavy Hitters with Strong Error Bounds	2009	PODS
7	6,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS
8	4,258	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD
9	7,831	Differentially Private Hierarchical Heavy Hitters	2024	PODS
10	5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB