Data structures for fast intersection operations?
<p>Randomly select two sets ,both set contains distinct keys (one key may belongs to multiple sets ,one set can never contain duplicate keys ).</p>

<p>Return a integer which represents for the number of keys belongs to both sets .</p>

<p>For example intersect({1,2,3,4},{3,4,5}) returns 2 .</p>

<p>I just need the size of the intersection .I don't need to know exactly which keys are there in the intersection .</p>

<p>Are there any datastructures support this kind of operations in <strong>less than O(n) time</strong> ?</p>

<p>Edit:</p>

<p><strong>Reading the data out does requires O(n) time</strong>, but <strong>that would not lead to the conclusion that you can't do the intersection operation in less than O(n) time</strong> .</p>

<p>Image this scenario:</p>

<p>I have N sets,each contains 100 keys . I read them up, that's N*100 operations .Now I want to know witch pair of sets have the largest intersection ,that's O(N²) intersection operations .So I want to reduce the complexity of the intersection operation .I don't really care how much time it takes to read and construct the sets ,it's at most N*100,that's nothing compares to O(N²) intersection operations .</p>

<p>Be aware ,there's no way that you can find the pair of sets that have the largest intersection by doing less than O(N²) intersection operations ,I can prove that .You <strong>must</strong> do all the intersection operations .</p>

<p>(he basic idea is ,let's imagine a complete graph ,with N vertices ,each represent for a set ,and Nx(N-1)/2 edges, each represents for a intersection for the connected pair .Now give each edge an non-negetive weight all you want(represents for the intersection size) ,I can always construct N sets satisfy those Nx(N-1)/2 edge weights .That proves my claim .)</p>