2018/07/17 by Chou, Chi-Ning, Lei, Zhixian, Nakkiran, Preetum
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1807.06479
The ℓ2 tracking problem is the task of obtaining a streaming algorithm that, given access to a stream of items a1,a2,a3,… from a universe [n], outputs at each time t an estimate to the ℓ2 norm of the frequency vector f(t)∈ ℝ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 an streaming algorithm with (the optimal) space using O(ε-2log(1/δ)) words and O(ε-2log(1/δ)) update time to obtain an ε-accurate estimate with probability at least 1-δ. We give the first algorithm that achieves update time of O(log 1/δ) which is independent of the accuracy parameter ε, together with the nearly optimal space using O(ε-2log(1/δ)) words. Our algorithm is obtained using the \textsfCountSketch of [Charilkar-Chen-Farach-Colton, ICALP 2002].