Data Structure for Set Intersection?
If each set maintains a record of what other sets exist, and you have a total of $s &gt; 0$ sets, you can easily turn any data structure for a collection (e.g. binary search trees, etc.) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.


Each set should have a unique identifier from some totally ordered set. If you explicitly name your sets $S_1, S_2, \ldots$ then the identifier could just be the index. 
You should implement a "registry" of the sets; a data structure which maintains a collection of all of the sets which you have defined. The registry should be implemented as a search-tree data structure, to allow easy retrieval (e.g.&nbsp;if you wish to delete the set) and linear-time traversal of the sets.
Each set $S_j$ also maintains an "index" of each of the other sets &mdash; not a copy of them, but rather a data structure which is indexed by the labels of the other sets. This index will be used to maintain, for each set $S_k$, a binary search tree of all of the elements of $S_j \cap S_k$. (The two sets $S_j$ and $S_k$ share one copy of that search tree.) 


Initialization 

Initialization of a set $T = \varnothing$ consists of $O(1)$ operations to initialize the tree of its elements, $O(s)$ operations as you initialize (copying from the registry) the index for the set $T$, and $O(s \log s)$ operations as you traverse the registry to add $T$ into the indices of each of the other sets $S_j$. In the index of $T$, we create search trees representing $T \cap S_j = \varnothing$ for the other sets $S_j$; we copy the same pointer for the index of $S_j$.

Adding an element to a set $T$

Adding some $x \in V$ to the set $T$ takes time $O(\log n_T)$ as usual, where $n_T = |T|$. We also test for membership of $x$ in each of the other sets $S_1, S_2, \ldots$, which takes time $$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$$ where $n = |V|$ is the size of the universe (or of the largest set $S_j$) and $s$ is the number of sets in the registry.
For each set $S_j$ such that $x \in S_j$, also insert $x$ into the index for the set $S_j \cap T$.
For each such set $S_j$, this takes $O(\log s + \log n_T)$ time, to look up  $S_j$ in the index of $T$ and to insert $x$ in $S_j \cap T$; across all sets $S_1, S_2, \ldots$ this takes time $O(s \log s + s \log n_T)$. If we suppose that the number of sets $S_j$ is much less than the size of the universe $V$ (that is, if we suppose $s \ll n$), the total time for element insertion is then $O(s \log n)$.

If you do not allow duplicates in sets, we can save time in the case that $x \in S$ already by forgoing the membership test and insertions for the other sets $T$. "Insertion" in the case that $x$ is already present then takes time only $O(\log n_T)$.

Intersection testing

The index of each set is maintained precisely in order to allow quick evaluation of whether or not two sets $S_j$ and $S_k$ intersect.
For a set $S_j$, simply by checking its index for the set $S_k$, we can not only determine in time $O(\log s)$ whether or not $S_j$ intersects $S_k$, but we can also retrieve a binary tree containing the entire set $S_j \cap S_k$.

Element Removal

To delete an element $x$ from a set $T$, we remove it not only from the search tree for $T$ itself, but from each of the intersections $S_j \cap T$ for the sets $S_j$ in its index. This takes time $O(s \log n_T)$, where $n_T = |T|$.

Set Deletion

Because of the overhead of searching the registry, if you have many sets, it may be desirable to delete sets once they are no longer needed.
By traversing the entire registry, we may delete $S$ from the index of all other sets $S_j$ in time $O(sn_T)$, dominated by the cost of deleting the search tree representing $S_j \cap T$ for each of the other sets $S_j$, where $n_T = |T|$.

Remarks

If you expect only to implement a constant number of sets, then the above run-times reduce to:


initialization: $O(1)$
element insertion: $O(\log n)$
intersection testing (and retrieval of the intersection): $O(1)$
element removal: $O(\log n_T)$
set deletion: $O(n_S)$


where $n$ is the size of the largest set in the registry, and $n_T = |T|$ for the set $T$ which you are operating on.

If you expect to have $O(|V|)$ sets, where $V$ is your universe, you may need a different data structure if you want these operations to operate in sub-linear time. However, if you have pairs of sets whose intersection you know you will never test, you might be able to reduce the size of the index for the sets (by not including any sets whose intersection you will test) or use more than one registry (one for each collection of sets whose intersection you might test). In fact, a registry is only useful if you want centralized control of ensuring that each pair of sets has a record of each other in the index: it may be practical in some cases, at the initialization of a set $S$, simply to record ad hoc each new set into the indices of the other sets $T$ whose intersection with $S$ you are interested in.