The only obstacle that prevents us from applying the \(L_1\)  sampling algorithm to the \(L_2\)  case is that we cannot compute exactly the 2-norm of the weighted vector \(\Vert \mathbf {w}_u^k\Vert _2\) . We can compute \(\Vert \mathbf {w}_u^k\Vert _1\)  without knowing the values \(\mathbf {f}_u^k[v]\)  in advance, \(v \in N_k(u)\) , but we need to know the values \(\mathbf {f}_u^k[v]^2\)  in order to compute the 2-norm of the weighted frequency vector. However, we can efficiently approximate the 2-norm of a vector revealed in a streaming fashion, this is a fundamental algorithmic problem for which algorithms with optimal computational complexity have been designed [1]}, [2]}. These algorithms can be adapted to the local graph neighborhood setting which yields the following result.
