Sampling from a moving window over streaming data

By Brian Babcock, Mayur Datar, Rajeev Motwani. ACM-SIAM Symposium on Discrete Algorithms, 2002

390 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/1291e22341cb130d1fd166f51f6d746ec5fe98a0

How researchers see this paper

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

Citations in the corpus

Online outlier detection in sensor data using non-parametric models (2006, methodology): “The algorithm [4] starts with an initial random sample, and proceeds as follows.”
Models and issues in data stream systems (2002, methodology): “In another paper, Babock, DatarandMotwani [9] adapt thereservoir sampling algorithm to thesliding windows case.”
Learning from Time-Changing Data with Adaptive Windowing (2007, methodology): “To reduce these costs we present a new version ADWIN2 using ideas developed in data stream algorithmics [1, 15, 2, 6] to find a good cutpoint quickly.”
Characterizing concept drift (2015, unknown): “…al., 2003b], DriftDetectionMethodClassiﬁer [Gama et al., 2004a], DriftDetectionMethodClassiﬁerEDDM [Baena-Garcıa et al., 2006], HoeﬀdingAdaptiveTree [Bifet and Gavald`a, 2009], HoeﬀdingOp-tionTree [Pfahringer et al., 2007], HoeﬀdingTree [Hulten et al., 2001 and Russell, 2001, Babcock et al., 2002].”
Processing Sliding Window Multi-Joins in Continuous Queries over Data Streams (2003, background): “The former is called a count-based, or a sequence-based sliding window, while the latter is called a time-based or a timestamp-based sliding window [5].”
Clustering Data Streams: Theory and Practice (2003, background): “…in small space when the data is a stream include: frequency estimation [36], [12], norm estimation [4], [22], [44], order statistics [64], [57], [56], [30], [28], synopsis structures [26], time indexed data [25], [32], [17], [8], signal reconstructions [24], [18], [1], [33], [27], [29], [72].”
Issues in data stream management (2003, background): “In addition to windowed sampling [7], a possible solution to computing sliding window queries in sublinear space is to divide the window into small portions (called basic windows in [72]) and only store a synopsis and a timestamp for each portion.”
Maintaining variance and k-medians over data stream windows (2003, background): “O Callaghan, N. Mishra, A. Meyerson, S. Guha, and R. Motwani.”
Learning to Classify With Incremental New Class (2021, unknown): “There are other topics in data stream mining [38].”
Evaluating window joins over unbounded streams (2003, background): “Recently a good deal of research has been conducted in this area: for example, stream sampling [27], updating summary data structures [36][40][37][41][38], and maintaining stream statistics [11].”
Streaming Pattern Discovery in Multiple Time-Series (2005, background): “In addition to system-building efforts, a number of approximation techniques have been studied in the context of streams, such as sampling [7], sketches [16, 10, 19], exponential histograms [13], and wavelets [22].”