Stanford InfoLab Publication Server

Maintaining Variance and k-Medians over Data Stream Windows

Babcock, Brian and Datar, Mayur and Motwani, Rajeev and O'Callaghan, Liadan (2003) Maintaining Variance and k-Medians over Data Stream Windows. In: ACM Symposium on Principles of Database Systems (PODS 2003), June 9-12, 2003, San Diego, California.


This is the latest version of this item.



We extend the work from our earlier paper in SODA 2002 to maintain complex statistics in the sliding window model that cannot be estimated using previous techniques. In particular we consider the following two problems and provide solutions to them that require very less memory: estimating the variance and maintaining the cluster centers (k-medians).

Item Type:Conference or Workshop Item (Paper)
Subjects:Computer Science > Data Streams
Related URLs:Project Homepage
ID Code:749
Deposited By:Import Account
Deposited On:08 Mar 2003 16:00
Last Modified:24 Dec 2008 08:34

Available Versions of this Item

Download statistics

Repository Staff Only: item control page