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: 1300
Venue: PODS
Year: 2003
Pagerank: 0.0001370404
Overall Rank: 838 | 94.26%
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
438	DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views	2012	VLDB	0.00018471721
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
2,128	Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling	2005	VLDB	9.1271562e-05
2,406	Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles	2005	SIGMOD	8.6187297e-05
2,698	Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores	2020	SIGMOD	8.2450522e-05
2,808	A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows	2006	PODS	8.1006881e-05
3,023	Persistent Data Sketching	2015	SIGMOD	7.8398269e-05
3,703	Approximation Techniques for Spatial Data	2004	SIGMOD	7.1829776e-05
3,832	Optimal Tracking of Distributed Heavy Hitters and Quantiles	2009	PODS	7.0856664e-05
4,005	Fast Data Stream Algorithms using Associative Memories	2007	SIGMOD	6.9643802e-05
4,258	Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data	2004	SIGMOD	6.7994155e-05
4,370	Fast Manhattan Sketches in Data Streams	2010	PODS	6.7387541e-05
4,381	Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams	2007	VLDB	6.7333392e-05
4,683	False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams	2004	VLDB	6.5641059e-05
5,036	Finding Hierarchical Heavy Hitters in Data Streams	2003	VLDB	6.3915389e-05
5,216	Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors	2005	SIGMOD	6.3121293e-05
6,060	Finding Global Icebergs over Distributed Data Sets	2006	PODS	5.9914746e-05
6,120	Finding Frequent Items in Probabilistic Data	2008	SIGMOD	5.9693818e-05
7,548	Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory	2024	SIGMOD	5.6021153e-05
7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	5.5610113e-05
7,751	GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks	2014	VLDB	5.552233e-05
7,752	Sketch-based Geometric Monitoring of Distributed Stream Queries	2013	VLDB	5.5521918e-05
8,106	SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model	2022	VLDB	5.4853605e-05
9,084	Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform	2013	PODS	5.3251649e-05
11,759	Timely Reporting of Heavy Hitters using External Memory	2020	SIGMOD	5.093636e-05
12,582	SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting	2008	VLDB	5.093636e-05
12,683	Deterministic K-Set Structure	2006	PODS	5.093636e-05
12,755	Using Association Rules for Fraud Detection in Web Advertising Networks	2005	VLDB	5.093636e-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
122	Approximate Frequency Counts over Data Streams	2002	VLDB	0.00031260115
149	New Sampling-Based Summary Statistics for Improving Approximate Query Answers	1998	SIGMOD	0.00029226907
235	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023783792
274	Balancing Histogram Optimality and Practicality for Query Result Size Estimation	1995	SIGMOD	0.00022645621
418	Tracking Join and Self-Join Sizes in Limited Storage	1999	PODS	0.00018812821
550	Distributed Top-K Monitoring	2003	SIGMOD	0.0001663758
577	Computing Iceberg Queries Efficiently	1998	VLDB	0.00016235949
842	How to Summarize the Universe: Dynamic Maintenance of Quantiles	2002	VLDB	0.00013671191

Semantically Similar Papers

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