Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
复制标题
DOI：
10.4230/lipics.approx-random.2018.7
复制
发表时间：
2018-05
期刊：
影响因子：
--
通讯作者：
V. Braverman;Elena Grigorescu;Harry Lang;David P. Woodruff;Samson Zhou
中科院分区：
文献类型：
--
作者：
V. Braverman;Elena Grigorescu;Harry Lang;David P. Woodruff;Samson Zhou
我们研究了滑动窗口模型中的不同元素和$\ell_p$-Heavy Hitters问题，其中只有数据流中最近的$n$元素形成了底层集合。我们首先介绍可组合直方图，这是指数直方图(Datar等人，Soda 2002)和平滑直方图(Braverman和Ostrovsky，FOCS 2007)的简单扭曲，可能是独立感兴趣的。然后，我们展示了可组合直方图以及跟踪少数特定项的身份或频率的现有技术的仔细组合，足以获得针对不同元素和$\ell_p$的算法-在$n$和$\epsilon$中几乎都是最优的。应用我们新的可组合直方图框架，我们提供了一个算法，该算法输出滑动窗口模型中不同元素的数目的$(1+\epsilon)$-近似值，并使用$\O{\frac{1}{\epsilon^2}\log n\log\frac{1}{\epsilon}\log\log n+\frac{1}{\epsilon}\log^2 n}$位的空间。对于$\ell_p$-重打击手，我们提供了一个对$0<；p\le 2$使用空间$\mathcal{O}\Left(\frac{1}{\epsilon^p}\log^2n\Left(\log\log n+\log\frac{1}{\epsilon}\right))$的算法，改进了最著名的$\ell_2$重打击手算法(Braverman等人，Cocoon 2014)，其空间复杂度为$\mathcal{O}\Left(\frac{1}{\silepon^4}\log^3 n\right)$。我们还证明了对于不同元素，$Omega\Left(\FRAC{1}{\epsilon}\LOG^2n+\FRAC{1}{\epsilon^2}\logn\Right)$和$\Omega\Left(\FRAC{1}{\epsilon^p}\log^2n\Right)$对于$\ell_p$-重打击者是几乎最优的下界，两者都紧到$\Mathcal{O}(\LOG\LOG n)$和$\mathcal{O}\left(\log\frac{1}{\epsilon}\right)$因子。
We study the distinct elements and $\ell_p$-heavy hitters problems in the sliding window model, where only the most recent $n$ elements in the data stream form the underlying set. We first introduce the composable histogram, a simple twist on the exponential (Datar et al., SODA 2002) and smooth histograms (Braverman and Ostrovsky, FOCS 2007) that may be of independent interest. We then show that the composable histogram along with a careful combination of existing techniques to track either the identity or frequency of a few specific items suffices to obtain algorithms for both distinct elements and $\ell_p$-heavy hitters that are nearly optimal in both $n$ and $\epsilon$. Applying our new composable histogram framework, we provide an algorithm that outputs a $(1+\epsilon)$-approximation to the number of distinct elements in the sliding window model and uses $\O{\frac{1}{\epsilon^2}\log n\log\frac{1}{\epsilon}\log\log n+\frac{1}{\epsilon}\log^2 n}$ bits of space. For $\ell_p$-heavy hitters, we provide an algorithm using space $\mathcal{O}\left(\frac{1}{\epsilon^p}\log^2 n\left(\log\log n+\log\frac{1}{\epsilon}\right)\right)$ for $0<p\le 2$, improving upon the best-known algorithm for $\ell_2$-heavy hitters (Braverman et al., COCOON 2014), which has space complexity $\mathcal{O}\left(\frac{1}{\epsilon^4}\log^3 n\right)$. We also show complementing nearly optimal lower bounds of $\Omega\left(\frac{1}{\epsilon}\log^2 n+\frac{1}{\epsilon^2}\log n\right)$ for distinct elements and $\Omega\left(\frac{1}{\epsilon^p}\log^2 n\right)$ for $\ell_p$-heavy hitters, both tight up to $\mathcal{O}(\log\log n)$ and $\mathcal{O}\left(\log\frac{1}{\epsilon}\right)$ factors.