Data structure for optimal deduplication of common subsets

Question

Consider a database with the following properties:

• It stores symbols (represented as 64-bit integers) and sets of symbols
• Sets may contain thousands of symbols, and there may be thousands of sets which are the same except for one or two added symbols
• Every set should have exactly one canonical representation (two identical sets must have identical representations in the database)

If several sets contain large common subsets, they should be highly compressible: it should be possible to represent the common subset as a set itself, and store a reference to it, similarly to most persistent data structures.

However, the requirement for a single canonical representation of a set complicates things. Inserting certain new elements may rearrange the entire data structure, removing shared subsets. What kind of data structure would allow for shared common subsets in the majority of cases? My first guess is a balanced binary tree, but I'm not sure if balancing is even necessary; all that's needed is for the same set of symbols to always result in the same tree.

Answer 1

What you're looking for here is the intersection of two classes of data structures:

• Persistent data structures, in which modifying a structure doesn't eliminate access to the old structure. This ensures that the shared parts don't have to be stored twice.
• Uniquely represented data structures, as required by your "one canonical representation" phrase.

Unfortunately, most persistent balanced tree data structures are not going to be uniquely represented. One that is uniquely represented is the sorted Braun tree, but they do not share a lot of structure, and two trees with $O(1)$ differences can have structures that are different in $\Omega(n)$ locations.

If you nest Braun trees within Braun trees, you can get this down to $O(\sqrt{n \log n})$.

However, since your symbols are 64-bit integers, you're in a good spot. You can use path-compressed tries, which have a unique representation. They use $\Theta(n)$ nodes to store a set of $n$ symbols, and adding or deleting a symbol to an existing set of symbols allows sharing almost all of the original structure: no more than $2 + \min(n,w)$ new nodes are created, where $w$ is the word width (64 for you).