
By linearity of expectation \(\mathbb {E}[\Vert \mathbf {w}_u^k\Vert _1]={O}(\Vert \mathbf {f}^k_{u}\Vert \log n)\) . Since the random numbers \(r_x\)  are independent by Hoeffdings's inequality we obtain that \(\Vert \mathbf {w}_u^k\Vert _1 = {O}(\Vert \mathbf {f}^k_{u}\Vert \log n)\)  almost surely. Note that \(\Vert \mathbf {w}_u^k\Vert _1\)  can be computed exactly at each node. Thus, we have shown that there exists a unique node \(x\)  with weight \(\Vert \mathbf {f}^k_{u}\Vert _1\)  and the total weight of the nodes in \(N_k(u)\)  is bounded by \({O}(\Vert \mathbf {f}^k_{u}\Vert _1\log n)\) . Using a deterministic frequent items mining algorithm like Frequent [1]} we can detect this unique heavy hitter using space \(O(\log n)\) . Since for all other nodes \(v \ne x\)  it holds \(\mathbf {w}^k_u[x] \le \Vert \mathbf {f}^k_{u}\Vert _1/2\) , by the main result from [1]} it follows that for a summary size of \(> 2 \log n\)  the heavy hitter will be the only node whose weight in the summary will be at least \(\Vert \mathbf {f}^k_{u}\Vert _1/2\) . Note that the summaries generated by Frequent are mergeable [3]}, and can be merged in time proportional to the number of elements stored in the summary. In each iteration we need to perform exactly \(m\)  such summary merges, thus each iteration over all nodes takes \(O(m\log n)\)  and needs space \(O(n \log n)\)
