An algorithm for sampling uniformly from the \(k\) -hop neighborhood of node \(u\)  easily follows. We implement a random permutation on the \(n\)  nodes by generating a random number for each node \(r: V \rightarrow \lbrace 0,1,\ldots ,\ell -1\rbrace \) . For a sufficiently large \(\ell \)  with high probability \(r\)  is a bijective function and thus it implements a random permutationFor example, for \(\ell = n^2/\delta \)  with probability at least \(1-\delta \)  the function is bijective.. For each node \(u\) , \(sketch_u\)  is initialized with \((r(u), u)\) , i.e., the sketch is just a single (random number, node) pair. The aggregation after each iteration is storing the pair with the smallest random number from \(u\) 's neighbors, \(sketch_u = \min _{(r_v, v): v \in N(u)}sketch_v\) . After \(k\)  iterations at each node \(u\)  we have stored the smallest number form the set \(\lbrace r(v): v \in N_k(u)\rbrace \) , i.e., we have sampled a node from \(N_k(u)\)  according to the permutation defined by the function \(r\) . Clearly, the samples for any two nodes \(u\)  and \(w\)  are coordinated as we work with the same permutation on the set \(N_k(u) \cup N_k(w)\) . The next theorem is a straightforward corollary from the main result on minwise-independent permutations [1]}:
