English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The task of finding heavy hitters is one of the best known and well studiedproblems in the area of data streams. One is given a list$i_1,i_2,\ldots,i_m\in[n]$ and the goal is to identify the items among $[n]$that appear frequently in the list. In sub-polynomial space, the strongestguarantee available is the $\ell_2$ guarantee, which requires finding all itemsthat occur at least $\epsilon\|f\|_2$ times in the stream, where the vector$f\in\mathbb{R}^n$ is the count histogram of the stream with $i$th coordinateequal to the number of times~$i$ appears $f_i:=\#\{j\in[m]:i_j=i\}$. The firstalgorithm to achieve the $\ell_2$ guarantee was the CountSketch of [CCF04],which requires $O(\epsilon^{-2}\log n)$ words of memory and $O(\log n)$ updatetime and is known to be space-optimal if the stream allows for deletions. Therecent work of [BCIW16] gave an improved algorithm for insertion-only streams,using only $O(\epsilon^{-2}\log\epsilon^{-1}\log\log n)$ words of memory. Inthis work, we give an algorithm \bptree for $\ell_2$ heavy hitters ininsertion-only streams that achieves $O(\epsilon^{-2}\log\epsilon^{-1})$ wordsof memory and $O(\log\epsilon^{-1})$ update time, which is the optimaldependence on $n$ and $m$. In addition, we describe an algorithm for tracking$\|f\|_2$ at all times with $O(\epsilon^{-2})$ memory and update time. Ouranalyses rely on bounding the expected supremum of a Bernoulli processinvolving Rademachers with limited independence, which we accomplish via aDudley-like chaining argument that may have applications elsewhere.

BPTree: an $\ell_2$ heavy hitters algorithm using constant memory