DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.2

Tracking the l_2 Norm with Constant Update Time

Authors: Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract

The l_2 tracking problem is the task of obtaining a streaming algorithm that, given access to a stream of items a_1,a_2,a_3,... from a universe [n], outputs at each time t an estimate to the l_2 norm of the frequency vector f^{(t)}in R^n (where f^{(t)}_i is the number of occurrences of item i in the stream up to time t). The previous work [Braverman-Chestnut-Ivkin-Nelson-Wang-Woodruff, PODS 2017] gave a streaming algorithm with (the optimal) space using O(epsilon^{-2}log(1/delta)) words and O(epsilon^{-2}log(1/delta)) update time to obtain an epsilon-accurate estimate with probability at least 1-delta. We give the first algorithm that achieves update time of O(log 1/delta) which is independent of the accuracy parameter epsilon, together with the nearly optimal space using O(epsilon^{-2}log(1/delta)) words. Our algorithm is obtained using the Count Sketch of [Charilkar-Chen-Farach-Colton, ICALP 2002].

Cite as

Chi-Ning Chou, Zhixian Lei, and Preetum Nakkiran. Tracking the l_2 Norm with Constant Update Time. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 2:1-2:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{chou_et_al:LIPIcs.APPROX-RANDOM.2019.2,
  author =	{Chou, Chi-Ning and Lei, Zhixian and Nakkiran, Preetum},
  title =	{{Tracking the l\underline2 Norm with Constant Update Time}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{2:1--2:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.2},
  URN =		{urn:nbn:de:0030-drops-112175},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.2},
  annote =	{Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch}
}

Search Results

Documents authored by Lei, Zhixian

Tracking the l_2 Norm with Constant Update Time

Abstract

Cite as

Thanks for your feedback!

Could not send message