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 23 of 73 citing papers.

Rank Citing Paper Year Venue Pagerank
7,280 PR-Sketch: Monitoring Per-key Aggregation of Streaming Data with Nearly Full Accuracy 2021 VLDB 5.5510741e-05
7,714 Local Differentially Private Heavy Hitter Detection in Data Streams with Bounded Memory 2024 SIGMOD 5.4557265e-05
7,814 Spatially-Decaying Aggregation Over a Network: Model and Algorithms 2004 SIGMOD 5.4310607e-05
7,895 Double-Anonymous Sketch: Achieving Top-K-fairness for Finding Global Top-K Frequent Items 2023 SIGMOD 5.4152499e-05
7,934 GeoScope: Online Detection of Geo-Correlated Information Trends in Social Networks 2014 VLDB 5.4072247e-05
7,935 Sketch-based Geometric Monitoring of Distributed Stream Queries 2013 VLDB 5.4071076e-05
8,040 LadderFilter: Filtering Infrequent Items with Small Memory and Time Overhead 2023 SIGMOD 5.3857229e-05
8,060 JoinSketch: A Sketch Algorithm for Accurate and Unbiased Inner-Product Estimation 2023 SIGMOD 5.382134e-05
8,119 Space Lower Bounds for Itemset Frequency Sketches 2016 PODS 5.3739121e-05
8,305 Experiences with Approximating Queries in Microsoft’s Production Big-Data Clusters 2019 VLDB 5.3427507e-05
8,411 Thread Cooperation in Multicore Architectures for Frequency Counting over Multiple Data Streams 2009 VLDB 5.3213581e-05
8,440 Optimal Approximate Matrix Multiplication over Sliding Windows 2026 VLDB 5.3148581e-05
9,517 SPAS: Continuous Release of Data Streams under w-Event Differential Privacy 2025 SIGMOD 5.151324e-05
11,593 A Universal Sketch for Estimating Heavy Hitters and Per-Element Frequency Moments in Data Streams with Bounded Deletions 2024 SIGMOD 4.9605343e-05
11,645 Enhancing Accuracy for Super Spreader Identification in High-Speed Data Streams 2024 VLDB 4.9605343e-05
11,718 Cache-Efficient Top-k Aggregation over High Cardinality Large Datasets 2024 VLDB 4.9605343e-05
11,995 Frequent Elements with Witnesses in Data Streams 2021 PODS 4.9605343e-05
12,112 Timely Reporting of Heavy Hitters using External Memory 2020 SIGMOD 4.9605343e-05
12,347 Runtime Optimization of Join Location in Parallel Data Management Systems 2017 VLDB 4.9605343e-05
12,516 Resource-oriented Approximation for Frequent Itemset Mining from Bursty Data Streams 2014 SIGMOD 4.9605343e-05
12,886 An Audit Environment for Outsourcing of Frequent Itemset Mining 2009 VLDB 4.9605343e-05
12,920 SLEUTH: Single-pubLisher attack dEtection Using correlaTion Hunting 2008 VLDB 4.9605343e-05
13,093 Using Association Rules for Fraud Detection in Web Advertising Networks 2005 VLDB 4.9605343e-05
Previous Page 2 / 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