Approximate counts and quantiles over sliding windows

By Arvind Arasu, Gurmeet Singh Manku. ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

379 citations recorded by the source corpus.

How researchers see this paper

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

Fast and approximate stream mining of quantiles and frequencies using graphics processors (2005, methodology): “In a stream with N values, a φ-quantile is defined as an element with rank dφNe and an -approximate quantile is any element whose rank is between d(φ− )Ne and d(φ+ )Ne [6].”
Data Streams: Models and Algorithms (Advances in Database Systems) (2006, background): “[20] Hastie T., Tibshirani R., Friedman J. (2001) The elements of statistical learning: data mining, inference, and prediction, New York: Springer.”
Theory and Practice of Bloom Filters for Distributed Systems (2012, neutral): “Techniques for space-efficient approximate counts over sliding windows ha ve been proposed in [37].”
PINT: Probabilistic In-band Network Telemetry (2020, methodology): “Further, we can use a sliding-window sketch (e.g., [5, 11, 13]) to reflect only the most recent measurements.”
A Fast Algorithm for Approximate Quantiles in High Speed Data Streams (2007, methodology): “log N)) and an average per-element update cost of O(log log N) if is fixed.”
Differentially Private Continual Monitoring of Heavy Hitters from Distributed Streams (2012, methodology): “Using the MG algorithm concurrently on overlapping blocks of different sizes, Arasu and Manku [1] gave a deterministic algorithm that continually estimate the count of every item with relative error λ with respect to the current window; the query and the update time is O( 1λ log 1 λ ), while O( 1 λ ”