What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically

Summary: Small-space dynamic algorithm that reports all hot (frequent) items under inserts and deletions with user-specified success probability and without rescanning the DB. Uses group-testing to achieve simple implementation and provable space/time/accuracy guarantees, unlike prior work. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h42369ac8d56f75ee
Venue: PODS
Year: 2003
Pagerank: 0.00013382689
Overall Rank: 860 | 94.24%
DOI: 10.1145/773153.773182

Incoming Non-self Citations Over Time

Authors

1. Graham Cormode (Rutgers University)
2. S. Muthukrishnan (Rutgers University)

BibTeX Citation

@inproceedings{cormode_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically}},
        url = {https://dl.acm.org/doi/10.1145/773153.773182},
        doi = {10.1145/773153.773182},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Cormode, Graham and Muthukrishnan, S.},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
408	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018836656
713	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014582248
2,184	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.8972748e-05
2,472	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.3988741e-05
2,667	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1324472e-05
2,887	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.8903242e-05
3,090	Persistent Data Sketching	2015	SIGMOD	7.6420011e-05
3,765	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0178846e-05
3,932	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.900511e-05
4,115	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.785832e-05
4,353	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6322269e-05
4,442	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5823839e-05
4,498	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5590284e-05
4,799	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.3945122e-05
5,179	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.225925e-05
5,336	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1613661e-05
6,201	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8350139e-05
6,267	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.8134046e-05
7,030	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.6006602e-05
7,714	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.4557265e-05
7,889	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	5.4159519e-05
7,934	GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks	2014	VLDB	5.4072247e-05
7,935	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4071076e-05
9,292	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.1860131e-05
12,112	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.9605343e-05
12,920	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	4.9605343e-05
13,021	Deterministic K-Set Structure	2006	PODS	4.9605343e-05
13,093	Using Association Rules for Fraud Detection in Web Advertising Networks	2005	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
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.0002855087
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
285	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022143946
432	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018400309
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016238411
591	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015853273
861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013374869

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	124	Approximate Frequency Counts over Data Streams	2002	VLDB
2	11,593	A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions	2024	SIGMOD
3	171	Wavelet-Based Histograms for Selectivity Estimation	1998	SIGMOD
4	745	Dynamic Multidimensional Histograms	2002	SIGMOD
5	4,799	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB
6	8,405	Mining Deviants in a Time Series Database	1999	VLDB
7	6,267	Finding Frequent Items in Probabilistic Data	2008	SIGMOD
8	861	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB
9	13,050	Scalable Continuous Query Processing by Tracking Hotspots	2006	VLDB
10	911	Finding Frequent Items in Data Streams	2008	VLDB