Variance Estimation over Sliding Windows

Summary: First work to close the complexity gap for ε-approximate variance over sliding windows, improving on prior O(1/ε^2 · log N) space vs. the Ω(1/ε · log N) lower bound. Achieves optimal O(1/ε · log N) space and O(1) worst-case update time. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1431
Venue: PODS
Year: 2007
Pagerank: 5.093636e-05
Overall Rank: 12,629 | 13.36%
DOI: 10.1145/1265530.1265562

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Linfeng Zhang (Iowa State University)
2. Yong Guan (Iowa State University)

BibTeX Citation

@inproceedings{zhang_pods07,
        address = {New York, NY, USA},
        series = {{PODS} '07},
        title = {{Variance Estimation over Sliding Windows}},
        url = {https://dl.acm.org/doi/10.1145/1265530.1265562},
        doi = {10.1145/1265530.1265562},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Zhang, Linfeng and Guan, Yong},
        year = {2007}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
668	StatStream: Statistical Monitoring of Thousands of Data Streams in Real Time	2002	VLDB	0.00015166017
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS	8.9331834e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,374	Optimal Matrix Sketching over Sliding Windows	2024	VLDB
2	82	Space-Efficient Online Computation of Quantile Summaries	2001	SIGMOD
3	2,576	Optimal Sampling from Sliding Windows	2009	PODS
4	11,123	Streaming Algorithms with Few State Changes	2024	PODS
5	12,026	Variability in Data Streams	2016	PODS
6	6,696	Matrix Sketching Over Sliding Windows	2016	SIGMOD
7	12,305	Space-Efficient Estimation of Statistics over Sub-Sampled Streams	2012	PODS
8	7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS
9	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
10	2,218	Maintaining Variance and k–Medians over Data Stream Windows	2003	PODS