<p>Hashing is usually an efficient technique for storage and retrieval of multidimensional data. Problem is here that the number of attributes is variable and potentially very large, right? I googled it a bit and found <a href="https://en.wikipedia.org/wiki/Feature_hashing" rel="nofollow noreferrer">Feature Hashing</a> on Wikipedia. The idea is basically the following:</p>

<ul>
<li>Construct a hash of fixed length from each data entry (aka feature vector)</li>
<li>The length of the hash must be much smaller than the number of available features. The length is important for the performance.</li>
</ul>

<p>On the wikipedia page there is an implementation in pseudocode (create hash for each feature contained in entry, then increase feature-vector-hash at this index position (modulo length) by one) and links to other implementations.</p>

<p>Also here on SO is a question about <a href="https://stackoverflow.com/questions/8673035/what-is-feature-hashing-hashing-trick">feature hashing</a> and amongst others a reference to a scientific paper about <a href="http://arxiv.org/pdf/0902.2206" rel="nofollow noreferrer">Feature Hashing for Large Scale Multitask Learning</a>.</p>

<p>I cannot give a complete solution but you didn't want one. I'm quite convinced this is a good approach. You'll have to play around with the length of the hash as well as with different hashing functions (bloom filter being another keyword) to optimize the speed for your special case. Also there might still be even more efficient approaches if for example retrieval speed is more important than storage (balanced trees maybe?).</p>
Need algorithm for fast storage and retrieval (search) of sets and subsets
<p>I need a way of storing sets of arbitrary size for fast query later on.
I'll be needing to query the resulting data structure for subsets or sets that are already stored.</p>

<p>===
Later edit: To clarify, an accepted answer to this question would be a link to a study that proposes a solution to this problem. I'm not expecting for people to develop the algorithm themselves.
I've been looking over the tuple clustering algorithm found <a href="http://www.cs.uoi.gr/~tsap/publications/limbo.pdf" rel="nofollow noreferrer">here</a>, but it's not exactly what I want since from what I understand it 'clusters' the tuples into more simple, discrete/aproximate forms and loses the original tuples.</p>

<p>Now, an even simpler example:</p>

<p><code>[alpha, beta, gamma, delta] [alpha, epsilon, delta] [gamma, niu, omega] [omega, beta]</code></p>

<p>Query:</p>

<p><code>[alpha, delta]</code></p>

<p>Result:</p>

<p><code>[alpha, beta, gama, delta] [alpha, epsilon, delta]</code></p>

<p>So the set elements are just that, unique, unrelated elements. Forget about types and values. The elements can be tested among them for equality and that's it.  I'm looking for an established algorithm (which probably has a name and a scientific paper on it) more than just creating one now, on the spot.</p>

<p>==
Original examples:</p>

<p>For example, say the database contains these sets<br></p>

<pre><code>[A1, B1, C1, D1], [A2, B2, C1], [A3, D3], [A1, D3, C1] 
</code></pre>

<p>If I use <code>[A1, C1]</code> as a query, these two sets should be returned as a result:<br></p>

<pre><code>[A1, B1, C1, D1], [A1, D3, C1]
</code></pre>

<p>Example 2:</p>

<p>Database:</p>

<pre><code>[Gasoline amount: 5L, Distance to Berlin: 240km, car paint: red]
[Distance to Berlin: 240km, car paint: blue, number of car seats: 2]
[number of car seats: 2, Gasoline amount: 2L]
</code></pre>

<p>Query:</p>

<pre><code>[Distance to berlin: 240km]
</code></pre>

<p>Result</p>

<pre><code>[Gasoline amount: 5L, Distance to Berlin: 240km, car paint: red]
[Distance to Berlin: 240km, car paint: blue, number of car seats: 2]
</code></pre>

<p>There can be an unlimited number of 'fields' such as <code>Gasoline amount</code>. A solution would probably involve the database grouping and linking sets having common states (such as <code>Gasoline amount: 240</code>) in such a way that the query is as efficient as possible.</p>

<p>What algorithms are there for such needs?</p>

<p>I am hoping there is already an established solution to this problem instead of just trying to find my own on the spot, which might not be as efficient as one tested and improved upon by other people over time.</p>

<p>Clarifications:</p>

<ul>
<li>If it helps answer the question, I'm intending on using them for storing states:
Simple example:
[Has milk, Doesn't have eggs, Has Sugar]</li>
<li>I'm thinking such a requirement might require graphs or multidimensional arrays, but I'm not sure</li>
</ul>

<p><strong>Conclusion</strong>
I've implemented the two algorithms proposed in the answers, that is <em>Set-Trie</em> and <em>Inverted Index</em> and did some rudimentary profiling on them. Illustrated below is the duration of a query for a given set for each algorithm. Both algorithms worked on the same randomly generated data set consisting of sets of integers. The algorithms seem equivalent (or almost) performance wise:</p>

<p><img src="https://i.stack.imgur.com/pVj7o.png" alt="enter image description here"></p>