Maintaining Stream Statistics over Sliding Windows

By Mayur Datar, Aristides Gionis, Piotr Indyk, Rajeev Motwani. SIAM journal on computing (Print), 2002

938 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/21d141bc7ae0046f4015321e7669f6259339fa17

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 Computational Theory and Mathematics

Citations in the corpus

One Sketch to Rule Them All: Rethinking Network Flow Monitoring with UnivMon (2016, background): “This derives from a rich literature in the theory community on streaming algorithms starting with the seminal “AMS” paper [9] and has since been an active area of research (e.g., [19, 24, 26, 28]).”
Foundations and Modeling of Dynamic Networks Using Dynamic Graph Neural Networks: A Survey (2020, methodology): “Overlapping snapshots such as sliding time-windows [37] are also used in dynamic network analysis to have less radical change from one network snapshot to the next [38].”
Maintaining variance and k-medians over data stream windows (2003, methodology): “Closing the gap between this upper bound on memory usage, and the lower bound of Ω( 1 2 log N), given by Datar et al.[7], is an open problem.”
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.”
Efficient Computation of Frequent and Top-k Elements in Data Streams (2005, background): “Problems studied in this context include approximate frequency moments [1], differences [20], distinct values estimation [22, 33, 45], bit counting [16], duplicate detection [42], approximate quantiles [28, 38, 40], histograms [30, 29], wavelet based aggregate queries [25, 41], correlated aggregate ”
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].”
Data streams: algorithms and applications (2005, methodology): “This model was proposed in [36] and is natural, but it is somewhat synthetic to put a hard bound of w on the window size, for example, irrespective of the rate of arrival of the strea m.”
Frequency Estimation of Internet Packet Streams with Limited Space (2002, background): “Some variants of this problem have been previously considered in the context of one pass analysis of database streams [1, 10, 20], query streams to a search engine [3], and packet data streams [7, 9, 19, 21].”
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].”
FetchSGD: Communication-Efficient Federated Learning with Sketching (2020, neutral): “Fortunately, this “sliding window” problem is well studied in the sketching community (Datar et al., 2002; Braverman and Ostrovsky, 2007), and it is possible to identify heavy hitters that are spread over a sequence of gradients with only log ( I ) error accumulation sketches.”
Adaptive Learning from Evolving Data Streams (2009, methodology): “Also important for our purposes,ADWIN does not maintain the window explicitly, but compresses it using a variant of the exponential histogram technique in [ 6 ].”
Models and issues in data stream systems (2002, background): “Designing sampling-based algorithms that can produce approximate answers that are provably close to the exact answer is an important and active area of research.”
Spectral bloom filters (2003, methodology): “The SBF can support both streaming data and sliding window data sets [6], given that old data is available for deletion.”
Online and Non-Parametric Drift Detection Methods Based on Hoeffding’s Bounds (2015, methodology): “In the following subsections we mention relevant algorithms used in online learning, which fall in two main categories: window strategies and weightedinstance approaches.”