ETD

• compression
• sets
• succinct data structures

This thesis studies compressed representations of collections of sets drawn from a common ordered universe. The representation must support standard ordered-set queries on each set: membership, access by position, rank (which counts elements up to a value), predecessor, and successor. A natural baseline is to compress each set in isolation, treating it only as a subset of the universe. Such an encoding may exploit the internal structure of each set, but it cannot use the redundancy that appears only when the sets are viewed together. Containment, overlap, and small differences between sets are precisely the regularities lost by this isolated view. Existing relation-based representations exploit these regularities by storing one set through another and answering queries along labelled trees. Their references, however, are usually restricted to the input sets or to a graph on them, so they do not measure how much information the whole collection contains.
To measure the redundancy that is visible only at the collection level, we change how we look at the collection. Instead of describing one set at a time, we look at each universe element and record which input sets contain it. Elements that appear in exactly the same input sets can be grouped together. If the groups that occur and their sizes are known, describing the collection reduces to deciding which labelled universe elements belong to each group. Counting these assignments gives a reference for the bits needed to describe how elements are distributed across the collection. Taken alone, however, this reference is only a count. It says how many bits are needed in principle, but not how to organize those bits so that membership, access, rank, predecessor, and successor on a single set can be answered without decoding the global assignment or adding separate indexes.
We introduce Set-Union Matching (SUM) to turn this counting view into a queryable hierarchy. Existing encodings can exploit a relation between two sets in two natural ways: if one contains the other, the smaller set can be recovered by deleting elements from the larger one, and if two sets are close, one can be described by recording the elements on which they differ. SUM keeps the first style by creating, for each chosen pair of current sets, their union as the smallest common parent, so that both children are recovered from the parent only by deleting the elements that do not belong to the corresponding child, and every edge in the hierarchy has the same containment meaning. Repeating this step in rounds builds a hierarchy of such parents, using the savings exposed by each union to decide which pairs to merge and keeping the least costly hierarchy reached by the construction. The resulting count never exceeds the isolated-set baseline and improves on it when the hierarchy captures shared structure, while the global assignment count remains the lower benchmark for the hierarchy model considered in the thesis. Because the hierarchy uses only containment edges, each connected part becomes a deletion tree, where a set is recovered from its root by removing the labels found along one root-to-leaf path. A dictionary for each root and path-query indexes on the tree, then support membership, access, rank, predecessor, and successor, with logarithmic terms governed by the root of that tree.