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: 1294
Venue: PODS
Year: 2003
Pagerank: 8.9331834e-05
Overall Rank: 2,218 | 84.79%
DOI: 10.1145/773153.773176

Incoming Non-self Citations Over Time

Authors

1. Brian Babcock (Stanford University)
2. Mayur Datar (Stanford University)
3. Rajeev Motwani (Stanford University)
4. Liadan O'Callaghan (Stanford University)

BibTeX Citation

@inproceedings{babcock_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Maintaining Variance and k–Medians over Data Stream Windows}},
        url = {https://dl.acm.org/doi/10.1145/773153.773176},
        doi = {10.1145/773153.773176},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Babcock, Brian and Datar, Mayur and Motwani, Rajeev and O'Callaghan, Liadan},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS	0.00014927798
2,340	Online Outlier Detection in Sensor Data Using Non-Parametric Models	2006	VLDB	8.7246796e-05
2,576	Optimal Sampling from Sliding Windows	2009	PODS	8.3964437e-05
5,260	Energy-Efficient Monitoring of Extreme Values in Sensor Networks	2006	SIGMOD	6.2956086e-05
5,802	Time-Decaying Aggregates in Out-of-order Streams	2008	PODS	6.0843083e-05
7,001	On Joining and Caching Stochastic Streams	2005	SIGMOD	5.7282075e-05
7,103	Efficient Adaptive Detection of Complex Event Patterns	2018	VLDB	5.7023779e-05
7,400	Effective Variation Management for Pseudo Periodical Streams	2007	SIGMOD	5.6255397e-05
7,695	A Shared Execution Strategy for Multiple Pattern Mining Requests over Streaming Data	2009	VLDB	5.5661355e-05
7,797	Better Sliding Window Algorithms to Maximize Subadditive and Diversity Objectives	2019	PODS	5.5422948e-05
12,629	Variance Estimation over Sliding Windows	2007	PODS	5.093636e-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
26	Models and Issues in Data Stream Systems	2002	PODS	0.00052982574
31	BIRCH: An Efficient Data Clustering Method for Very Large Databases	1996	SIGMOD	0.00050347119
311	Surfing Wavelets on Streams: One-Pass Summaries for Approximate Aggregate Queries	2001	VLDB	0.00021760621
351	CURE: An Efficient Clustering Algorithm for Large Databases	1998	SIGMOD	0.00020424271
4,222	Density Biased Sampling: An Improved Method for Data Mining and Clustering	2000	SIGMOD	6.8227421e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,603	Stream Frequency over Interval Queries	2019	VLDB
2	12,026	Variability in Data Streams	2016	PODS
3	2,716	Space- and Time-Efficient Deterministic Algorithms for Biased Quantiles over Data Streams	2006	PODS
4	5,385	Randomized Error Removal for Online Spread Estimation in Data Streaming	2021	VLDB
5	7,713	Sketch-based Querying of Distributed Sliding-Window Data Streams	2012	VLDB
6	2,576	Optimal Sampling from Sliding Windows	2009	PODS
7	3,657	Memory-Limited Execution of Windowed Stream Joins	2004	VLDB
8	2,610	Maintaining Time-Decaying Stream Aggregates	2003	PODS
9	691	Approximate Counts and Quantiles over Sliding Windows	2004	PODS
10	12,629	Variance Estimation over Sliding Windows	2007	PODS