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 ?


When you want to know about a specific problem, it is always good to start with reading a recent paper. I recommend you to read this paper and the references therein.

Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011)

| cite | improve this answer | |
  • 3
    $\begingroup$ I think it would help improve the answer to make it a bit more self-contained by briefly saying what they do in the paper. $\endgroup$ – usul Aug 6 '14 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.