<p>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.</p>

<p><a href="http://dl.acm.org/citation.cfm?id=1938550" rel="nofollow">Bolin Ding, Arnd Christian König: Fast Set Intersection in Memory. PVLDB 4(4): 255-266 (2011)</a></p>

CC BY-SA 3.0
2014-08-06T21:09:40.053Z
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.
usul
CC BY-SA 3.0
2014-08-06T14:04:45.317Z
2014-08-06T14:04:45.317Z
Hiroki Yanagisawa
<p>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)</p>

<p>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)</p>

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

<cc.complexity-theory><ds.data-structures>
what is known about efficient set intersections
josinalvo
# what is known about efficient set intersections

(Asked by: username_0 on 2014-08-02)

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 ?

**Tags:** cc.complexity-theory, ds.data-structures


---

## 1 answers

### Answer by username_1 on 2014-08-06. Score: 3

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)](http://dl.acm.org/citation.cfm?id=1938550)

> **Comments:**
> **username_2**: 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.  

---

