License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.2
URN: urn:nbn:de:0030-drops-112175
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11217/
Chou, Chi-Ning ;
Lei, Zhixian ;
Nakkiran, Preetum
Tracking the l_2 Norm with Constant Update Time
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].
BibTeX - Entry
@InProceedings{chou_et_al:LIPIcs:2019:11217,
author = {Chi-Ning Chou and Zhixian Lei and Preetum Nakkiran},
title = {{Tracking the l_2 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 = {Dimitris Achlioptas and L{\'a}szl{\'o} A. V{\'e}gh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11217},
URN = {urn:nbn:de:0030-drops-112175},
doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.2},
annote = {Keywords: Streaming algorithms, Sketching algorithms, Tracking, CountSketch}
}
|
Keywords: |
|
Streaming algorithms, Sketching algorithms, Tracking, CountSketch |
|
Collection: |
|
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
17.09.2019 |
