set representation question

[Nicholas Nethercote]

On Wed, 12 Nov 2003, Tom Pledger wrote:

> Hal Daume III writes:
>  :
>  | *all* i care about is being able to quickly calculate the size of
>  | the intersection of two sets.  these sets are, in general, very
>  | sparse, which means that the intersections tend to be small.
>  |
>  | for example, i might have two sets reprsented by the arrays:
>  |
>  |  {0,1,10,346,398,1039,3289,3853,9811,89231,50913}
>  |  {0,3,98,183,398,1038,5319,7642,9811,13893,93123}
>  |
>  | and all i need to be able to do is respond with "3" very very
>  | quickly.  using sorted arrays, this takes O(n+m) time (where n and
>  | m are the sizes of the arrays).
>
> The total time (including the up front time for building the data
> structure) can't go below O(n+m), because if it did, you'd be
> neglecting to look at some of the elements at all.

Isn't it O(min(m,n))?  You don't have to look at all elements for the
intersection.  Eg:

  {0,1,10}
  {0,3,98,183,398,1038,5319,7642,9811,13893,93123}

I can vaguely imagine some clever bitset implementation that lets you do
intersection with bitwise-and.  Mercury has a bitmap library, which might
be able to do something like this, but I'm not sure;  it might be more
suited to smaller and denser sets than you seem to have.  But it might be
worth a look (see www.cs.mu.oz.au/research/mercury/information/doc-release/library_8.html#SEC8)

N