Data structure for finding min of set intersection

From: Adam Morrison (adam.morrison_at_pobox.com)
Date: 11/15/04 

Date: 15 Nov 2004 04:17:34 -0800

Consider the following problem: We are given $m$ subsets $S_1,...,S_m$
of ${1,...,n}$. The goal is to build a data structure that supports a
MIN_INTERSECTION(i,j) operation, which returns the minimum number in the
intersection of $S_i$ and $S_j$. Is there such a data structure that
does better than the obvious $O(n)$ scheme of finding the intersection
and returning the minimum? (I'm mostly interested in fast MIN_INTERSECTION;
after that, in minimizing the space requirements of the data structure;
and least of all in the time it takes to build it.)

Is this a known/easy problem? I haven't found any relevant references
in the literature. In fact I didn't find much discussion of intersection
problems in general sets (i.e. not computational geometry). Any pointers
or ideas would be much appreciated!

Thanks,

  Adam