Consider $n$ sets of values (represented as sorted arrays with no duplicates, and with a known size (ie. the size can be obtained in O(1)). The values can be tested for equality in O(1) time. I want to obtain the set of values that are present in at least $k$ different sets among the $n$.
The obvious algorithm to do this is to go through all the sets, count the number of occurrences of each value, and return those with a count higher than $k$. Yet, in some cases, you can do better: for instance, when $n = k = 2$ and when one set $S_1$ is much smaller than the other set $S_2$, it is more efficient to look at all items of $S_1$ and perform a binary search for each of them in $S_2$: the binary search approach costs $O(|S_1| \log(|S_2|))$ whereas the naive approach costs $O(|S_1| + |S_2|)$ which is worse when $|S_1| << |S_2|$.
With this in mind, in which situations can we do better than the naive algorithm? (If this is a well-known problem, I would be happy to know its usual name and have references.)