# what is known about efficient set intersections

Say you have a number of sets of integers ($S_1, S_2 ... S_n$), and you want to calculate intersections of some of them ($\cap S_1, S_3, S_7$ might be a query, but you want to support many such queries, or maybe even all possible queries)

There is an obvious way to do this in linear time. Are there data-structures that allow for sub-linear time ? (of course, that is not be possible in general: the answer itself might have linear size. But an algorithm might have some other useful properties, like being linear on the answer size, or running on sub-linear time and giving just part of the intersection)

In general, what is the state of the problem? What approaches are known, and what is known to be hard ?