Space-optimal Heavy Hitters with Strong Error Bounds by Berinde, Radu, Indyk, Piotr, Cormode, Graham, Strauss, Martin J.

“…The problem of finding heavy hitters and approximating the frequencies of items is at the heart of many problems in data stream analysis. …”
Get full text
Get full text

Sketching via hashing: from heavy hitters to compressed sensing to sparse fourier transform by Indyk, Piotr

Get full text
Get full text

MacroBase: Prioritizing Attention in Fast Data by Abuzaid, Firas, Bailis, Peter, Ding, Jialin, Gan, Edward, Madden, Samuel, Narayanan, Deepak, Rong, Kexin, Suri, Sahaana

“…MacroBase is able to deliver order-of-magnitude speedups over alternatives by optimizing the combination of explanation (i.e., feature selection) and classification tasks and by leveraging a new reservoir sampler and heavy-hitters sketch specialized for fast data streams. …”
Get full text

Pseudo-deterministic streaming by Goldwasser, Shafrira, Grossman, Ofer.

“…Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, `2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) are not pseudo-deterministic. …”
Get full text