$k$-Multiset intersection efficient algorithm

Given a collection of sets $C= \{S_1,S_2,\cdots,S_n\}$ such that each set $S_i \in C$ is sorted and has at least $k$ elements.

What is the most efficient algorithm for finding the intersection of these sets: $\bigcap_{S_i \in C}{S_i}$

• @Raphael I tried having a universal set that contains all elements in the sets, then iterate these elements and check their existence in $S_i$. I am looking for a better algorithm. – M.M Jun 15 '15 at 12:19
• – Raphael Jun 15 '15 at 12:55

If the least elements in all $S_i$ are equal then pick it for final set else pick least element among all $S_i$ and remove (remove minimum among all sets and not minimums of all sets). This works in $O(n*|C|*log |C|)$, where $|C|$ is the total number of elements in $C$ (not it's cardinality). This works since all your $Si$ are sorted and removal of element will maintain the sorted order.