文章基本信息

标题：Continuous Monitoring of l_p Norms in Data Streams
本地全文：下载
作者：Jaroslaw Blasiok ; Jian Ding ; Jelani Nelson 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：81
页码：32:1-32:13
DOI：10.4230/LIPIcs.APPROX-RANDOM.2017.32
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In insertion-only streaming, one sees a sequence of indices a_1, a_2, ..., a_m in [n]. The stream defines a sequence of m frequency vectors x(1), ..., x(m) each in R^n, where x(t) is the frequency vector of items after seeing the first t indices 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 in [m]. Naively this guarantee is obtained by devising an algorithm with failure probability less than 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 l_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. In this work, we improve the state of the art for all 0
关键词：data streams; continuous monitoring; moment estimation