Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?
If each set maintains a record of what other sets exist, and you have a total of $s > 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. 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 — 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.
There are data structures that allow you to do this in less than linear time, even for worst-case inputs. See https://www.microsoft.com/en-us/research/wp-content/uploads/2011/01/p255-DingKoenig.pdf (and the papers references in there).
If your two sets S and T have a large intersection and you have a dictionary for S, looking up elements of T in random order should quickly give you a common element. The most difficult case is when the intersection size is 0 or 1.
Usually your programming language of choice will support a data structure with unique elements. In general there are three popular approaches: Trees, Hashes and Bitmasks. Tree elements must be comparable, Hash elements must be hashable and Bitmask elements must have some way of conversion to integers.
A tree-set will support insertion in O(log n) and intersection testing in Worst Case O(n log n).
A hash-set will support insertion in Amortized O(1*h) where 'h' is the running time of the hashing algorithm, and intersection test in Worst Case O(n).
Bitmask sets are not generally used like tree- and hash-sets.
If your case allows false positive answers, I'd use Bloom Filter with a single hash function.
You can implement it as follows :
Init an empty set
Add an element to a set.
Given two sets(B1,B2), report whether they intersect.
Complexity
The keyword to search for is inverted indexes, this kind of data structure is very common in that context.
Depending on what your set elements look like, tries allow for sub-linear time merging if the two subsets have mostly-disjoint prefixes. Computing the intersection runs in O(𝛿(log(n_1/𝛿) + log(n_2/𝛿))) , where 𝛿 is often called the alternation measure.
The other approach is to use bitmaps of various kinds, which tend to have very good constant factors on intersection because intersections are parallelism & SIMD friendly. A previous answer mentioned bloom filters which fit in that category and give approximate results, but they can be efficient for exact approaches as well if compressed hierarchical bitmaps are used. Roaring bitmaps are widely used: https://arxiv.org/pdf/1402.6407
