2017/04/21 by Jarosław Błasiok, Jian Ding, Błasiok, Jarosław +3 · 1 citation
Computer Science · #Complexity and Algorithms in Graphs #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1704.06710
openalex publication_date 2017/04/21 · openalex created_date 2017/05/05 · openalex updated_date 2026/07/28
In insertion-only streaming, one sees a sequence of indices a1, a2, …, am∈ [n]. The stream defines a sequence of m frequency vectors x(1),…,x(m)∈ℝn with (x(t))i = |\j : j∈[t], aj = i\|. That is, x(t) is the frequency vector after seeing the first t items in the stream. Much work in the streaming literature focuses on estimating some function f(x(m)). Many applications though require obtaining estimates at time t of f(x(t)), for every t∈[m]. Naively this guarantee is obtained by devising an algorithm with failure probability ≪ 1/m, then performing a union bound over all stream updates to guarantee that all m estimates are simultaneously accurate with good probability. When f(x) is some ℓp norm of x, recent works have shown that this union bound is wasteful and better space complexity is possible for the continuous monitoring problem, with the strongest known results being for p=2 [HTY14, BCIW16, BCINWW17]. In this work, we improve the state of the art for all 0