Forty years of frequent items
From MaRDI portal
Summary: We survey the last 40 years of algorithm development for finding frequent items in data streams, a line of work which surprisingly wound up developing new tools in information theory, pseudorandomness, chaining methods for bounding suprema of stochastic processes, and spectral graph theory. For the entire collection see [Zbl 07816360].
Cites work
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- An improved data stream summary: the count-min sketch and its applications
- An information statistics approach to data stream and communication complexity
- Asymptotically optimal lower bounds on the NIH-multi-party information complexity of the AND-function and disjointness
- Beating CountSketch for heavy hitters in insertion streams
- Communication Complexity
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Finding frequent items in data streams
- Finding repeated elements
- Heavy Hitters and the Structure of Local Privacy
- Hellinger Strikes Back: A Note on the Multi-party Information Complexity of AND
- scientific article; zbMATH DE number 53996 (Why is no real title available?)
- scientific article; zbMATH DE number 3518027 (Why is no real title available?)
- scientific article; zbMATH DE number 3551902 (Why is no real title available?)
- scientific article; zbMATH DE number 7711619 (Why is no real title available?)
- Linear-time encodable and decodable error-correcting codes
- Local, private, efficient protocols for succinct histograms
- On the boundedness of Bernoulli processes
- Practical locally private heavy hitters
- Random sampling with a reservoir
- Regularity of Gaussian processes
- Suprema of chaos processes and the restricted isometry property
- Theory of Cryptography
This page was built for publication: Forty years of frequent items
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6198649)
