DBScholar

Back to papers

Approximate Counts and Quantiles over Sliding Windows

Summary: Deterministic and randomized algorithms for ε-approximate frequency counts and quantiles over both fixed-size and adversarial variable-size sliding windows, using O((1/ε) polylog(1/ε,N)) space. Improves prior quantile bounds from O(1/ε^2) and gives the first space-efficient bounds for sliding-window frequency counts. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID
hc410e4c2143123ee
Venue
PODS
Year
2004
Pagerank
0.00014582248
Overall Rank
713 | 95.23%
DOI
10.1145/1055558.1055598

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{arasu_pods04,
        address = {New York, NY, USA},
        series = {{PODS} '04},
        title = {{Approximate Counts and Quantiles over Sliding Windows}},
        url = {https://dl.acm.org/doi/10.1145/1055558.1055598},
        doi = {10.1145/1055558.1055598},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Arasu, Arvind and Manku, Gurmeet Singh},
        year = {2004}
}

Incoming Citations (Sorted by Pagerank)

Showing 32 of 32 citing papers.

Rank Citing Paper Year Venue Pagerank
770 VerdictDB: Universalizing Approximate Query Processing 2018 SIGMOD 0.00014086699
911 Finding Frequent Items in Data Streams 2008 VLDB 0.00013093314
1,290 Resource Sharing in Continuous Sliding-Window Aggregates 2004 VLDB 0.00011151196
2,040 Database Learning: Toward a Database that Becomes Smarter Every Time 2017 SIGMOD 9.1319608e-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,887 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS 7.8903242e-05
3,090 Persistent Data Sketching 2015 SIGMOD 7.6420011e-05
3,667 Quantiles over Data Streams: An Experimental Study 2013 SIGMOD 7.0967962e-05
3,714 Space Complexity of Hierarchical Heavy Hitters in Multi-Dimensional Data Streams 2005 PODS 7.0553175e-05
4,279 Relative Error Streaming Quantiles 2021 PODS 6.6731371e-05
4,353 Diamond in the Rough: Finding Hierarchical Heavy Hitters in Multi-Dimensional Data 2004 SIGMOD 6.6322269e-05
4,401 Beyond Simple Aggregates: Indexing for Summary Queries 2011 PODS 6.6051378e-05
4,744 KLL± Approximate Quantile Sketches over Dynamic Datasets 2021 VLDB 6.4278327e-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,932 Time-Decaying Aggregates in Out-of-order Streams 2008 PODS 5.9261324e-05
6,201 Finding Global Icebergs over Distributed Data Sets 2006 PODS 5.8350139e-05
6,855 Matrix Sketching Over Sliding Windows 2016 SIGMOD 5.6470368e-05
7,415 Together is Better: Heavy Hitters Quantile Estimation 2023 SIGMOD 5.5160692e-05
7,978 Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives 2019 PODS 5.3978826e-05
8,129 Logging Every Footstep: Quantile Summaries for the Entire History 2010 SIGMOD 5.3739121e-05
8,440 Optimal Approximate Matrix Multiplication over Sliding Windows 2026 VLDB 5.3148581e-05
8,792 Stream Frequency over Interval Queries 2019 VLDB 5.2629414e-05
8,800 CoopStore: Optimizing Precomputed Summaries for Aggregation 2020 VLDB 5.2602992e-05
9,160 Modeling Skew in Data Streams 2006 SIGMOD 5.2037189e-05
9,592 Optimal Matrix Sketching over Sliding Windows 2024 VLDB 5.1376962e-05
10,746 Quantile Estimation with Duplicates 2026 SIGMOD 4.9605343e-05
11,332 Approximation-First Timeseries Query At Scale 2025 VLDB 4.9605343e-05
11,928 Efficient and Error-bounded Spatiotemporal Quantile Monitoring in Edge Computing Environments 2022 VLDB 4.9605343e-05
12,703 FIFO Indexes for Decomposable Problems 2011 PODS 4.9605343e-05
12,967 Variance Estimation over Sliding Windows 2007 PODS 4.9605343e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 11 of 11 cited papers.

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

Rank Cited Paper Year Venue Pagerank
13 Mining Association Rules between Sets of Items in Large Databases 1993 SIGMOD 0.0006440069
26 Models and Issues in Data Stream Systems 2002 PODS 0.00051942573
82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD 0.00036097627
124 Approximate Frequency Counts over Data Streams 2002 VLDB 0.00030503973
152 Query Processing, Resource Management, and Approximation in a Data Stream Management System 2003 CIDR 0.00028566618
153 New Sampling-Based Summary Statistics for Improving Approximate Query Answers 1998 SIGMOD 0.0002855087
252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD 0.00023058622
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
860 What’s Hot and What’s Not: Tracking Most Frequent Items Dynamically 2003 PODS 0.00013382689
2,274 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS 8.7041791e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 6,637 Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald 2024 PODS
2 4,023 Optimal Bounds for Approximate Counting 2022 PODS
3 252 Approximate Medians and other Quantiles in One Pass and with Limited Memory 1998 SIGMOD
4 2,738 Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams 2006 PODS
5 2,274 Maintaining Variance and k–Medians over Data Stream Windows 2003 PODS
6 4,975 A Tight Lower Bound for Comparison-Based Quantile Summaries 2020 PODS
7 4,279 Relative Error Streaming Quantiles 2021 PODS
8 12,967 Variance Estimation over Sliding Windows 2007 PODS
9 82 Space-Efficient Online Computation of Quantile Summaries 2001 SIGMOD
10 2,887 A Simpler and More Efficient Deterministic Scheme for Finding Frequent Items over Sliding Windows 2006 PODS