<p>[This solution is similar to Louis Ricci's, except inverted to the Topics table - <em>which could make subscription updates less practical, be warned!</em>] </p>

<p><em>(The probabilistic data structure approach is cool, but unnecessary for your current data-size.  I was initially looking at compressed bitsets for a non-probabilistic solution, as they are great at performing set operations in-memory, but I think that's overkill as well.  <a href="http://arxiv.org/pdf/1402.6407.pdf" rel="nofollow">Here is a good implementation for this type of use-case.</a> if you're interested.)</em></p>

<p>But looking at the <em>sparsity</em> of your data, bitsets waste space over integer-arrays.  And even with integer-arrays, the <code>union</code> operation is still pretty inexpensive given that <strong>you only have an average of 10,000 subscriptions per topic.</strong> </p>

<hr>

<p>So maybe, just maybe, a dead-simple data-structure given your use-case is simply:</p>

<pre><code>Topic 1 =&gt; [array of subscriber IDs]
Topic 2 =&gt; [array of subscriber IDs]
...
Topic 20,000 =&gt; [array of subscriber IDs]
</code></pre>

<p><em>Storing (avg) 10,000 subscriber IDs (assuming 32-bit integers) only requires about <strong>40kb</strong> of space per topic.</em>  </p>

<p>[In an array-type or BLOB, depending on your database]</p>

<p><em>With 20,000 topics, this adds only 800mb of data to your topic table ... and very little of this (~200kb avg) needs to be loaded to memory when a notification event occurs!</em></p>

<hr>

<p>Then when an average event (affecting 5 topics) occurs, all that needs to happen is:</p>

<ol>
<li><p>Query / Pull the data for the relevant topics (avg 5 records) into memory
(<strong>avg ~200kb</strong> of I/O)</p></li>
<li><p>Dump them into a Set data structure (de-duplicates subscriber list)</p></li>
<li><p>Alert the subscribers in the Set.</p></li>
</ol>
Is there a probabilistic data structure for storing relations?
<p>I have database with user subscriptions to topics.
There is currently about 20 000 topics,
20 mln users and 200 mln subscriptions stored in SQL database.
Because of its size, the database is partitioned by topics,
so I can't get the info in one database query.
There are couple of topics with 10 mln subscriptions, couple with 100 000 and others have hundreds or less.</p>

<p>When an event occurs, it usually matches couple of topics, so to inform users, I need to perform query like "give me all users subscribed to topics x, y, z and perform union of sets", so that one user gets the news once even if he subscribed both topics x and z.</p>

<p>The constraints are:</p>

<ul>
<li>There must be no duplicates in the union set. (users can't get the content twice)</li>
<li>There can be bounded amount of users missing from the union set. (if sometimes user doesn't get the content, it is not that bad, but it can't be always the same user for the same topic)</li>
<li>It is possible to subscribe to new topic without rebuilding whole thing.</li>
</ul>

<p>I thought about using set of bloom filters for every topic, but they constraints are the other way round: "user either not subscribed for sure or probably subscribed". I need something like "user subscribed for sure or probably not".</p>

<p>Lossy hash tables might be good idea, but I am not sure, if they can be as memory efficient as bloom filters and I am afraid, that it would be always the same user, that is missing the content in his topic.</p>

<p>Do you know any other data structures, that mey be good for solving this problem?</p>