DBScholar

Back to papers

Approximate Frequency Counts over Data Streams

Summary: Memory-efficient streaming frequency-count algorithms with provable error bounds for threshold-exceeding items. Handles both singleton-item streams (IP monitoring) and set-valued streams; includes a single-pass, optimized frequent itemset computation. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
h73090b3bbd96f117
Venue
VLDB
Year
2002
Pagerank
0.00030503973
Overall Rank
124 | 99.18%
DOI
10.1016/B978-155860869-6/50038-X

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{manku_vldb02,
        title = {{Approximate Frequency Counts over Data Streams}},
        author = {Manku, Gurmeet Singh and Motwani, Rajeev},
        journal = {PVLDB},
        series = {{VLDB} '02},
        doi = {10.1016/B978-155860869-6/50038-X},
        url = {https://doi.org/10.1016/B978-155860869-6/50038-X},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 73 citing papers.

Rank Citing Paper Year Venue Pagerank
26 Models and Issues in Data Stream Systems 2002 PODS 0.00051942573
254 The History of Histograms (abridged) 2003 VLDB 0.00022999992
565 Distributed Top-K Monitoring 2003 SIGMOD 0.00016238411
713 Approximate Counts and Quantiles over Sliding Windows 2004 PODS 0.00014582248
841 Quickr: Lazily Approximating Complex AdHoc Queries in BigData Clusters 2016 SIGMOD 0.00013503124
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
874 Spectral Bloom Filters 2003 SIGMOD 0.00013298839
891 E-Store: Fine-Grained Elastic Partitioning for Distributed Transaction Processing Systems 2015 VLDB 0.00013211469
911 Finding Frequent Items in Data Streams 2008 VLDB 0.00013093314
1,070 Sketching Streams Through the Net: Distributed Approximate Query Tracking 2005 VLDB 0.0001215545
1,471 Communication-Efficient Distributed Monitoring of Thresholded Counts 2006 SIGMOD 0.00010529345
1,639 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS 9.9845484e-05
1,903 Cold Filter: A Meta-Framework for Faster and More Accurate Stream Processing 2018 SIGMOD 9.383454e-05
2,063 Space Efficient Mining of Multigraph Streams 2005 PODS 9.0815237e-05
2,130 Tributaries and Deltas: Efficient and Robust Aggregation in Sensor Network Streams 2005 SIGMOD 8.9875498e-05
2,184 Summarizing and Mining Inverse Distributions on Data Streams via Dynamic Inverse Sampling 2005 VLDB 8.8972748e-05
2,202 Graph Stream Summarization: From Big Bang to Big Crunch 2016 SIGMOD 8.861907e-05
2,232 Effective Phrase Prediction 2007 VLDB 8.7867154e-05
2,430 gSketch: On Query Estimation in Graph Streams 2012 VLDB 8.4651179e-05
2,472 Holistic Aggregates in a Networked World: Distributed Tracking of Approximate Quantiles 2005 SIGMOD 8.3988741e-05
2,633 Optimal Sampling from Sliding Windows 2009 PODS 8.1798806e-05
2,658 A Geometric Approach to Monitoring Threshold Functions Over Distributed Data Streams 2006 SIGMOD 8.1455298e-05
2,749 Sketching Probabilistic Data Streams 2007 SIGMOD 8.0426455e-05
2,938 Data Sketches for Disaggregated Subset Sum and Frequent Item Estimation 2018 SIGMOD 7.8224388e-05
3,091 Holistic UDAFs at Streaming Speeds 2004 SIGMOD 7.6394636e-05
3,525 Sketching Linear Classifiers over Data Streams 2018 SIGMOD 7.2156031e-05
3,543 Multidimensional Content eXploration 2008 VLDB 7.1968304e-05
3,559 Approximately Detecting Duplicates for Streaming Data using Stable Bloom Filters 2006 SIGMOD 7.1850048e-05
3,714 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 7.0553175e-05
3,932 Optimal Tracking of Distributed Heavy Hitters and Quantiles 2009 PODS 6.900511e-05
3,955 Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks 2012 PODS 6.8843906e-05
4,115 Fast Data Stream Algorithms using Associative Memories 2007 SIGMOD 6.785832e-05
4,330 On Biased Reservoir Sampling in the Presence of Stream Evolution 2006 VLDB 6.6454689e-05
4,353 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.6322269e-05
4,570 Approximate Frequency Counts over Data Streams 2012 VLDB 6.5162084e-05
4,799 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB 6.3945122e-05
5,040 Finding Persistent Items in Data Streams 2017 VLDB 6.2901248e-05
5,140 Shape Sensitive Geometric Monitoring 2008 PODS 6.2436669e-05
5,336 Fast and Approximate Stream Mining of Quantiles and Frequencies Using Graphics Processors 2005 SIGMOD 6.1613661e-05
5,341 Sampling Algorithms in a Stream Operator 2005 SIGMOD 6.1596655e-05
5,525 Time Adaptive Sketches (Ada-Sketches) for Summarizing Data Streams 2016 SIGMOD 6.0809613e-05
5,837 Pre-training Summarization Models of Structured Datasets for Cardinality Estimation 2022 VLDB 5.9600736e-05
6,057 Remembrance of Streams Past: Overload-Sensitive Management of Archived Streams 2004 VLDB 5.8838023e-05
6,138 Approximate Distinct Counts for Billions of Datasets 2019 SIGMOD 5.8575652e-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
6,446 A Regression-Based Temporal Pattern Mining Scheme for Data Streams 2003 VLDB 5.7665263e-05
6,570 An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems 2016 PODS 5.7279868e-05
6,855 Matrix Sketching Over Sliding Windows 2016 SIGMOD 5.6470368e-05
7,030 SpaceSaving±: An Optimal Algorithm for Frequency Estimation and Frequent Items in the Bounded-Deletion Model 2022 VLDB 5.6006602e-05
Previous Page 1 / 2 Next

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank Cited Paper Year Venue Pagerank
29 Fast Algorithms for Mining Association Rules 1994 VLDB 0.00051028332
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036097627
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
165 Mining Frequent Patterns without Candidate Generation 2000 SIGMOD 0.00027323925
251 An Effective Hash-Based Algorithm for Mining Association Rules 1995 SIGMOD 0.00023079256
316 Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries 2001 VLDB 0.00021238056
404 Bottom-Up Computation of Sparse and Iceberg CUBEs 1999 SIGMOD 0.00019034819
442 Random Sampling Techniques for Space Efficient Online Computation of Order Statistics of Large Datasets 1999 SIGMOD 0.00018182341
477 Sampling Large Databases for Association Rules 1996 VLDB 0.00017624579
566 On Computing Correlated Aggregates Over Continual Data Streams 2001 SIGMOD 0.00016236872
577 An Efficient Algorithm for Mining Association Rules in Large Databases 1995 VLDB 0.00016116712
591 Computing Iceberg Queries Efficiently 1998 VLDB 0.00015853273
951 Aqua: A Fast Decision Support System Using Approximate Query Answers 1999 VLDB 0.00012886042
1,006 Dynamic Maintenance of Wavelet-Based Histograms 2000 VLDB 0.00012551491
1,883 Efficient Computation of Iceberg Cubes with Complex Measures 2001 SIGMOD 9.4237043e-05
4,467 Online Association Rule Mining 1999 SIGMOD 6.5739122e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 11,593 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD
2 2,887 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS
3 3,284 Processing Set Expressions over Continuous Update Streams 2003 SIGMOD
4 1,639 Space-optimal Heavy Hitters with Strong Error Bounds 2009 PODS
5 1,329 Augmented Sketch: Faster and More Accurate Stream Processing 2016 SIGMOD
6 8,792 Stream Frequency over Interval Queries 2019 VLDB
7 11,995 Frequent Elements with Witnesses in Data Streams 2021 PODS
8 4,799 False Positive or False Negative: Mining Frequent Itemsets from High Speed Transactional Data Streams 2004 VLDB
9 12,516 Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams 2014 SIGMOD
10 911 Finding Frequent Items in Data Streams 2008 VLDB