Maintaining variance and k-medians over data stream windows

By Brian Babcock, Mayur Datar, Rajeev Motwani, Liadan O'Callaghan. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2003

323 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f8ed630b4d7e1731f95c43c58faa76c7b7012bb2

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Synopsis diffusion for robust aggregation in sensor networks (2004, background): “There has been a flurry of recent work in the data stream community devising clever synopses to answer aggregate queries on data streams (see [2, 24] for surveys, and [3, 7] for some more recent work).”
Approximate counts and quantiles over sliding windows (2004, background): “Sliding window algorithms have been developed for a variety of problems: bit-counting (Datar et al [9]), sampling (Babcock et al [3]), variance and k-medians (Datar et al [4], distinct values and bit-counts (Gibbons and Tirthapura [14]) and quantiles (Lin et al [17]).”
On evaluating stream learning algorithms (2012, methodology): “Recent learning algorithms such as Cormode, Muthukrishnan, and Zhuang (2007); Babcock, Datar, Motwani, and O’Callaghan (2003); Rodrigues, Gama, and Pedroso (2008) for clustering, Domingos and Hulten (2000); Hulten, Spencer, and Domingos (2001); Gama, Rocha, and Medas (2003); Liang, Zhang, and Song…”
Issues in evaluation of stream learning algorithms (2009, background): “Most recent learning algorithms [6, 1, 10, 20, 15, 12] maintain a decision model that continuously evolve over time, taking into account that the environment is non-stationary and computational resources are limited.”
Mining data streams: a review (2005, methodology): “[7] have used exponential histogram (EH) data structure to improve Guha et al.”
Online outlier detection in sensor data using non-parametric models (2006, methodology): “The estimate for the standard deviation of the sliding window is computed using a concise histogram along the time axis [5].”
Density-based clustering for real-time stream data (2007, background): “Movingwindow techniques are proposed to partially address this problem [2, 4].”
Issues in data stream management (2003, methodology): “This method may be used to compute correlations between streams [72], find frequently appearing items [24], and compute various aggregates [8, 23, 35].”