Database Paper Browser

Back to papers

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
1301
Venue
PODS
Year
2003
Pagerank
0.00015808172
Overall Rank
865 | 93.99%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 28 of 28 citing papers.

Rank Citing Paper Year Venue Pagerank
586 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00019685374
848 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.0001597308
2,282 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1073603e-05
2,759 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 8.1636123e-05
2,931 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 7.8697258e-05
3,543 Approximation Techniques for Spatial Data 2004 SIGMOD 6.9917053e-05
3,544 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 6.9898874e-05
3,566 Fast Manhattan Sketches in Data Streams 2010 PODS 6.9629443e-05
3,614 Persistent Data Sketching 2015 SIGMOD 6.9147318e-05
3,860 Fast Data Stream Algorithms using Associative Memories 2007 SIGMOD 6.6902516e-05
4,249 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.3245666e-05
4,334 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.2798179e-05
4,447 Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams 2007 VLDB 6.1791516e-05
4,449 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.1780147e-05
5,016 Finding Hierarchical Heavy Hitters in Data Streams 2003 VLDB 5.7580375e-05
5,457 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.4970777e-05
5,796 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3240234e-05
6,362 SLEUTH: Single-publisher attack detection Using correlation Hunting 2008 VLDB 5.0953013e-05
6,431 Finding Global Icebergs over Distributed Data Sets 2006 PODS 5.0654592e-05
6,599 Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory 2024 SIGMOD 4.9973567e-05
7,699 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6746076e-05
7,748 GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks 2014 VLDB 4.661103e-05
7,834 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 4.6382551e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5596344e-05
9,060 Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform 2013 PODS 4.4039656e-05
11,562 Timely Reporting of Heavy Hitters using External Memory 2020 SIGMOD 4.1945683e-05
12,490 Deterministic K-Set Structure 2006 PODS 4.1945683e-05
12,562 Using Association Rules for Fraud Detection in Web Advertising Networks 2005 VLDB 4.1945683e-05
Previous Page 1 / 1 Next

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
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036625711
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
327 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027308479
549 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020376603
597 Computing Iceberg Queries Efficiently 1998 VLDB 0.00019475592
745 Distributed Top-K Monitoring 2003 SIGMOD 0.00017330487
956 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015066967
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
166 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00039361552
10,983 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD 4.1945683e-05
222 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032828302
852 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015941524
4,449 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.1780147e-05
8,218 Mining Deviants in a Time Series Database 1999 VLDB 4.5566051e-05
5,796 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3240234e-05
956 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015066967
12,519 Scalable Continuous Query Processing by Tracking Hotspots 2006 VLDB 4.1945683e-05
835 Finding Frequent Items in Data Streams 2008 VLDB 0.00016109621