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.8738166e-05
Overall Rank: 2,403 | 83.31%
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
846	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00015949293
2,635	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.4081184e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
5,500	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD	5.4733109e-05
5,602	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	5.4153555e-05
6,532	Effective Variation Management for Pseudo Periodical Streams	2007	SIGMOD	5.0195121e-05
6,758	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	4.9335749e-05
6,852	On Joining and Caching Stochastic Streams	2005	SIGMOD	4.9027621e-05
7,316	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	4.7594979e-05
7,418	A Shared Execution Strategy for Multiple Pattern Mining Requests over Streaming Data	2009	VLDB	4.7306322e-05
12,444	Variance Estimation over Sliding Windows	2007	PODS	4.1905499e-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.00077399244
43	Models and Issues in Data Stream Systems	2002	PODS	0.00072660894
340	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00026854084
344	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00026698826
4,177	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.3768049e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,831	Variability in Data Streams	2016	PODS	4.1905499e-05
8,592	Stream Frequency over Interval Queries	2019	VLDB	4.4848323e-05
2,952	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS	7.8230109e-05
7,839	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB	4.6338068e-05
4,912	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB	5.8342232e-05
2,807	Optimal Sampling from Sliding Windows	2009	PODS	8.096649e-05
4,139	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB	6.4126764e-05
2,094	Maintaining Time-Decaying Stream Aggregates	2003	PODS	9.5556069e-05
846	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00015949293
12,444	Variance Estimation over Sliding Windows	2007	PODS	4.1905499e-05