<p>The following paper presents algorithms for union, intersection and difference on ordered sets that beat O(Z) if the intersection is larger than the difference (Z > n/2):</p>

<p><a href="http://arxiv.org/abs/1301.3388" rel="nofollow">Confluently Persistent Sets and Maps</a></p>
Fastest Set Operations In The West
<p>I haven't been able to find any satisfactory coverage of this topic all in one place, so I was wondering:
What are the fastest set intersect, union, and disjoin algorithms?<br>
Are there any interesting ones with limited domains?<br>
Can anyone beat O(Z) where Z is the actual size of intersection?</p>

<p>If your approach relies on sorted sets, please note that, but don't consider it a disqualifying factor.  It seems to me that there must be a veritable storehouse of subtle optimizations to be shared, and I don't want to miss any of them.</p>

<p>A few algorithms I know rely on bitwise operations beyond the vanilla, so you may assume the presence of SSE4 and access to intrinsics like popcount.  Please note this assumption.</p>

<p>Of interest:
<a href="http://fawx.com/2009/10/26/an-ode-to-set-intersection-part-1/" rel="noreferrer">An Implementation of B-Y Intersect</a></p>

<p><strong>Update</strong><br>
We've got some really good partial answers, but I'm still hoping for some more complete attacks on the problem.  I'm particularly interested in seeing a more fully articulated use of bloom filters in attacking the problem.</p>

<p><strong>Update</strong><br>
I've done some preliminary work on combining bloom filters with a cuckoo hash table.  It's looking almost obnoxiously promising, because they have very similar demands.  I've gone ahead and accepted an answer, but I'm not really satisfied at the moment.</p>