Maintaining Variance and k–Medians over Data Stream Windows

Summary: Sliding-window streaming algorithms: variance estimator with relative error ε using O((1/ε^2) log N) space. Also a constant-factor approximate k‑median for last N points using O((1/τ) k^4 N^{2τ} log^2 N) space, τ<1/2 trades space for approximation O(2^{O(1/τ)}). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1295
Venue: PODS
Year: 2003
Pagerank: 8.8837279e-05
Overall Rank: 2,404 | 83.28%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
2,629	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4160309e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
5,488	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD	5.4782627e-05
5,594	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4192122e-05
6,535	Effective Variation Management for Pseudo Periodical Streams	2007	SIGMOD	5.0243433e-05
6,755	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9383139e-05
6,853	On Joining and Caching Stochastic Streams	2005	SIGMOD	4.9070864e-05
7,318	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	4.7638874e-05
7,419	A Shared Execution Strategy for Multiple Pattern Mining Requests over Streaming Data	2009	VLDB	4.7348504e-05
12,435	Variance Estimation over Sliding Windows	2007	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
33	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00077324389
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072723062
341	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026810548
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026702512
4,177	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.3835403e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,823	Variability in Data Streams	2016	PODS	4.1945683e-05
8,594	Stream Frequency over Interval Queries	2019	VLDB	4.4891331e-05
2,955	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8239173e-05
7,834	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	4.6382551e-05
4,905	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	5.8398332e-05
2,789	Optimal Sampling from Sliding Windows	2009	PODS	8.1249652e-05
4,133	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4196026e-05
2,090	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5647927e-05
848	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.0001597308
12,435	Variance Estimation over Sliding Windows	2007	PODS	4.1945683e-05