title: Efficient set intersection - decide whether the intersection is larger than k
body: <p>I am faced with a problem where I have to calculate intersections between all pairs in a collection of sets. None of the sets are smaller than a small constant <em>k</em>, and I'm only interested in whether two sets have an intersection larger than <em>k</em>-1 elements or not. I do not need the actual intersections nor the exact size, <em>only</em> whether it's larger than <em>k</em>-1 or not. Is there some clever pre-processing trick or a neat set intersection algorithm that I could use to speed things up?</p>
  
  <p>More info that can be useful to answer the question:</p>
  
  <ul>
  <li>The sets represent maximal cliques in a large, undirected, sparse graph. The number of sets can be in the order of tens of thousands or more, but most of the sets are likely to be small.</li>
  <li>The <strike>sets are already sorted</strike> members of each set are in increasing order. Effectively they are sorted lists - I receive them this way from an underlying library for maximal clique search.</li>
  <li>Nothing is known about the distribution of elements in the sets (i.e. whether they are in tight clumps or not).</li>
  <li>Most of the set intersections are likely to be empty, so the ideal solution would be a clever data structure that helps me cut down the number of set intersections I have to make.</li>
  </ul>