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.000134266
Overall Rank: 858 | 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.00018900199
710	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014608975
2,171	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	8.9239861e-05
2,465	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.4253671e-05
2,664	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.1569551e-05
2,875	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	7.9193665e-05
3,080	Persistent Data Sketching	2015	SIGMOD	7.6662346e-05
3,758	Approximation Techniques for Spatial Data	2004	SIGMOD	7.0437238e-05
3,917	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	6.9266831e-05
4,097	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.8092798e-05
4,348	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.6469144e-05
4,446	Fast Manhattan Sketches in Data Streams	2010	PODS	6.5969248e-05
4,474	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.5838686e-05
4,778	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.4174716e-05
5,157	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.2494766e-05
5,327	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.1783009e-05
6,188	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.8571256e-05
6,252	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.8354449e-05
7,694	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.4764188e-05
7,697	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4754508e-05
7,870	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	5.4362374e-05
7,914	GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks	2014	VLDB	5.4277245e-05
7,916	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.4276156e-05
9,258	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.2056825e-05
12,062	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	4.9793485e-05
12,872	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	4.9793485e-05
12,973	Deterministic K-Set Structure	2006	PODS	4.9793485e-05
13,045	Using Association Rules for Fraud Detection in Web Advertising Networks	2005	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
153	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00028633995
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023363722
283	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022214789
428	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.0001845349
565	Distributed Top-K Monitoring	2003	SIGMOD	0.00016296423
588	Computing Iceberg Queries Efficiently	1998	VLDB	0.00015906635
862	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013396995

Semantically Similar Papers

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