More Like this

1. Pseudo-Deterministic Streaming

   https://doi.org/10.4230/LIPIcs.ITCS.2020.79  

   Goldwasser, Shafi; Grossman, Ofer; Mohanty, Sidhanth; Woodruff, David P. (January 2020, ITCS)
2. Relative Error Streaming Quantiles

   https://doi.org/10.1145/3452021.3458323  

   Cormode, Graham; Karnin, Zohar; Liberty, Edo; Thaler, Justin; Veselý, Pavel (June 2021, PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems)

   null (Ed.)
3. Relative Error Streaming Quantiles

   https://doi.org/10.1145/3542700.3542717  

   Cormode, Graham; Karnin, Zohar; Liberty, Edo; Thaler, Justin; Vesely, Pavel (May 2022, ACM SIGMOD Record)

   Estimating ranks, quantiles, and distributions over streaming data is a central task in data analysis and monitoring. Given a stream of n items from a data universe equipped with a total order, the task is to compute a sketch (data structure) of size polylogarithmic in n. Given the sketch and a query item y, one should be able to approximate its rank in the stream, i.e., the number of stream elements smaller than or equal to y. 

   more » « less
4. Streaming Complexity of SVMs

   Andoni, Alexandr; Burns, Collin; Li, Yi; Mahabadi, Sepideh; Woodruff, David (January 2020, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020))

   null (Ed.)
5. Streaming Periodicity with Mismatches

   Ergun, F; Grigorescu, E.; Sadeqi Azer, E.; Zhou, S. (August 2017, RANDOM)

   We study the problem of finding all $$k$$-periods of a length-$$n$$ string $$S$$, presented as a data stream. $$S$$ is said to have $$k$$-period $$p$$ if its prefix of length $n-p$ differs from its suffix of length $n-p$ in at most $$k$$ locations. We give a one-pass streaming algorithm that computes the $$k$$-periods of a string $$S$$ using $$\poly(k, \log n)$$ bits of space, for $$k$$-periods of length at most $$\frac{n}{2}$$. We also present a two-pass streaming algorithm that computes $$k$$-periods of $$S$$ using $$\poly(k, \log n)$$ bits of space, regardless of period length. We complement these results with comparable lower bounds. 

   more » « less