We use two sketching techniques, HyperLogLog [1]}, [2]} and MinHashing [3]}.
Given sets \(A\)  and \(B\) , HyperLogLog efficiently estimates the cardinality of the union \(|A \cup B|\)  and MinHashing estimates the Jaccard index \(J(A,B) = |A\cap B| / |A \cup B|\) . We combine these approaches to estimate the intersection of node sets produced by graph traversals  [4]}.
These techniques represent sets as sketches, where the sketches are much smaller than the sets they represent. Each technique has a parameter \(p\)  controlling the trade-off between the accuracy and computational cost. Running times for merging two sets, adding an element to a set, and extracting estimates only depend on \(p\) , but they are constant with respect to the size of the set. Importantly, the sketches of the union of sets are given by permutation-invariant operations (element-wise \(\min \)  for minhash and element-wise \(\max \)  for hyperloglog).
More details are provided in Appendix REF .
