Compact Data Structures for Set Collections
BSc thesis · DTU · Spring 2026 · graded 12/12 (highest on the Danish scale)
Five months of independent research on one question: when a collection of sets is nested, meaning every set sits largely inside a parent, can you store it in less space than an entropy compressed baseline? Most of the literature treats that baseline as the practical floor. On genuinely nested data the answer is yes, by 47 percent on the encoding, and this page explains the idea in about a minute of reading.
the problem
A collection of sets shows up constantly: adjacency lists in a graph, sparse bitvectors, genomic search indexes, any versioned or append only store. The obvious way to store one is to store each set on its own. A set of n elements drawn from a universe of size u needs lg(u choose n) bits, and doing that for every set costs the worst case entropy H(S), the sum of lg(u choose n_i). For sets with nothing in common that is essentially optimal.
It stops being optimal the moment the sets overlap. If one set sits entirely inside another, encoding both against the full universe pays twice for every element they share. That repeated payment is the shared structure the whole thesis is about.
the idea: describe each set against its parent
If S_i is a subset of S_j, then S_i does not need to be described as a subset of the universe. It only needs to be described as a subset of S_j. There are only (|S_j| choose |S_i|) ways to do that, never more and usually far fewer than (u choose |S_i|) ways. So give every set a parent p(S_i), the smallest set in the collection that contains it, and store each set as a bitvector of length |p(S_i)| where a 1 in position j means the jth element of the parent is also in this set. Sets with no proper superset get the universe as their parent.
Take three sets in the universe U = {1, ..., 8}: S1 = {1, 3, 5, 7}, S2 = {1, 5, 7}, and S3 = {5, 7}. S3 sits inside S2, which sits inside S1. Watch what happens to the bits when each set stops describing itself against the universe and starts describing itself against its parent:
total 24 bits
every set pays for all 8 universe positions, even the ones its parent already rules out.
That is the whole idea. Summed over the collection it gives the containment entropy L(S), the sum of lg(|p(S_i)| choose |S_i|), which is never larger than H(S) and is strictly smaller as soon as any set has a superset in the collection.
compressing one bitvector
Every node in the tree, and every set in the baseline, is stored with the same block based combinatorial encoding, so the comparison is like for like. Cut the bitvector into fixed blocks of b bits. Describe each block by two numbers: its class c, meaning how many 1s it holds, and its offset, meaning which of the (b choose c) patterns of that class it is.
Take b = 4 and the block 1010. It has two 1s, so its class is 2. The six patterns with exactly two 1s, in increasing numeric order, are:
0011, 0101, 0110, 1001, 1010, 1100 0 1 2 3 4 5
1010 is at index 4, so the pair (class 2, offset 4) identifies it exactly. The offset needs ceil(lg 6) = 3 bits rather than the 4 raw bits, and the gap widens as b grows. Blocks that are all 0s or all 1s have one possible pattern and need no offset bits at all. The list is never actually written out: a precomputed table of binomial coefficients, which is just Pascal's triangle, computes the offset directly and reverses it on decode. Summed over the vector, the offsets approach lg(u choose n), the information theoretic floor, with the class array and a few checkpoints as bounded overhead on top.
queries: the set no longer knows its own values
Storing a set against its parent creates a problem. A 1 in position j means "the jth element of my parent", which is meaningless until it has been translated all the way up to the universe. Both query operations are that translation.
Retrieve, which answers "what is the kth element of this set", walks up: at each level a select turns the current index into a position inside the parent. Rank, which answers "how many elements of this set are at most k", has to go up and then back down, because k is a universe value that none of the intermediate sets can interpret. Step through both on the same three sets:
retrieve(S3, 2): the 2nd one in S3 = 011 sits at position 3. Ask S2 for its 3rd element.
Both operations do constant work per level, so both cost O(depth). Which makes depth the thing that decides whether any of this is usable.
contraction: flattening the tree
Pointing every set at its smallest superset is optimal for space and terrible for depth. On the nested dataset it produces one chain 63 levels long, so a query walks 63 levels. Contraction fixes this by pointing each set instead at the highest ancestor of size at most twice its own. Two steps up the contracted chain therefore more than double the set size, so the chain can only be about lg u long before it reaches the universe, which caps depth at O(log u) and gives queries a cost of O(log(u / |S|)).
Take eight nested sets where set j has exactly j elements, so S1 is the smallest. Flip the switch and watch the chain fold: S1 (size 1) points at the highest ancestor of size at most 2, which is S2. S2 points at the highest of size at most 4, which is S4. S4 points at the highest of size at most 8, which is S8.
steps from S1 to the root: 7
pointing every set at its smallest superset is optimal for space, but on nested data the chain is as long as the collection. A query walks all of it.
contraction off: S1 through S8 to the universe, 7 steps
Same sets, a third of the walk. The cost is real and bounded: a set encoded against a larger parent produces a denser relative bitvector, so the encoding grows from 0.68 to 1.43 bits per element. In exchange the maximum depth falls from 63 to 5.6, the mean from 31.5 to 2.83, and retrieve goes from 7.88 to 0.82 microseconds. That is the trade the structure exists to make.
results
All figures below are from the nested dataset of 64 sets over a universe of 512 values, block size b = 16, contraction on unless stated, each the mean of 8 seeds.
axis: bits per element. Dashed bars are theoretical bounds, solid bars are measured. Each measured bar sits above its own bound, roughly 0.7 bits for the baseline and 0.4 for the hierarchy. That gap is block coding overhead, not a failure of the bound.
what contraction buys and costs, nested data
two of the three improve and one gets worse. Roughly 10x faster retrieve and 7x faster rank, bought with about 0.75 extra bits per element.
axis: percent space saved against the baseline. The query index adds roughly 10 to 11 bits per element to both structures, almost all of it the select array, which the thesis names as the obvious future work. On independent data there is no containment to exploit and the hierarchy is slightly larger.
Verification: 2 datasets × 8 seeds × 5 block sizes × 2 contraction settings, 160 configurations in total. Every one was checked against a brute force reference before any timing was trusted, and all 160 answered every retrieve and rank query correctly.
what it does not do
The structure is slower than the baseline on every query, 1.3x on retrieve and 1.7x on rank, and 4.4x to 6x slower to build. On sets that are mostly disjoint it saves nothing and costs a little, because the hierarchy flattens into a list and L falls back onto H. Once the query index is counted, the saving on favourable data drops from 47 percent to 14 percent, because the select array is a fixed per element cost that neither method avoids. For a read heavy workload on a collection that fits comfortably in memory, the simpler baseline is the better engineering choice. The structure earns its place on data that is genuinely nested and where space is the binding constraint, such as versioned or append only collections, and category trees where a child label's members are a subset of the parent's.
The scale is small and worth stating plainly: 64 sets, a universe of 512 values, synthetic data generated in memory with a seeded xorshift generator, eight seeds per configuration.