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.0001568356
Overall Rank
874 | 93.93%
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
585 DBToaster: Higher-order Delta Processing for Dynamic, Frequently Fresh Views 2012 VLDB 0.00019682634
846 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00015949293
2,269 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 9.1507118e-05
2,766 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 8.1559016e-05
2,934 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 7.8628636e-05
3,540 Approximation Techniques for Spatial Data 2004 SIGMOD 6.9922652e-05
3,545 Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores 2020 SIGMOD 6.9831585e-05
3,557 Fast Manhattan Sketches in Data Streams 2010 PODS 6.9711051e-05
3,618 Persistent Data Sketching 2015 SIGMOD 6.9080647e-05
3,863 Fast Data Stream Algorithms using Associative Memories 2007 SIGMOD 6.6838674e-05
4,246 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.318484e-05
4,450 Proof-Infused Streams: Enabling Authentication of Sliding Window Queries On Streams 2007 VLDB 6.1734998e-05
4,451 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.172063e-05
4,463 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.1563782e-05
5,188 Finding Hierarchical Heavy Hitters in Data Streams 2003 VLDB 5.635103e-05
5,465 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 5.491937e-05
5,807 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3189104e-05
6,426 Finding Global Icebergs over Distributed Data Sets 2006 PODS 5.0605823e-05
6,600 Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory 2024 SIGMOD 4.9925547e-05
7,697 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 4.6701245e-05
7,749 GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks 2014 VLDB 4.6566429e-05
7,839 Sketch-based Querying of Distributed Sliding-Window Data Streams 2012 VLDB 4.6338068e-05
8,203 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 4.5552628e-05
8,932 Sketching via Hashing: From Heavy Hitters to Compressive Sensing to Sparse Fourier Transform 2013 PODS 4.4229886e-05
11,566 Timely Reporting of Heavy Hitters using External Memory 2020 SIGMOD 4.1905499e-05
12,397 SLEUTH: Single-publisher attack detection Using correlation Hunting 2008 VLDB 4.1905499e-05
12,499 Deterministic K-Set Structure 2006 PODS 4.1905499e-05
12,571 Using Association Rules for Fraud Detection in Web Advertising Networks 2005 VLDB 4.1905499e-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
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
184 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.00036655704
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
328 Balancing Histogram Optimality and Practicality for Query Result Size Estimation 1995 SIGMOD 0.00027301497
550 Tracking Join and Self-Join Sizes in Limited Storage 1999 PODS 0.00020346247
598 Computing Iceberg Queries Efficiently 1998 VLDB 0.00019431661
743 Distributed Top-K Monitoring 2003 SIGMOD 0.00017318557
955 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015069776
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
168 Approximate Frequency Counts over Data Streams 2002 VLDB 0.0003915627
10,986 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD 4.1905499e-05
223 Wavelet-Based Histograms for Selectivity Estimation 1998 SIGMOD 0.00032829841
849 Dynamic Multidimensional Histograms 2002 SIGMOD 0.00015919478
4,451 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.172063e-05
8,216 Mining Deviants in a Time Series Database 1999 VLDB 4.5522552e-05
5,807 Finding Frequent Items in Probabilistic Data 2008 SIGMOD 5.3189104e-05
955 How to Summarize the Universe: Dynamic Maintenance of Quantiles 2002 VLDB 0.00015069776
12,528 Scalable Continuous Query Processing by Tracking Hotspots 2006 VLDB 4.1905499e-05
831 Finding Frequent Items in Data Streams 2008 VLDB 0.00016094846