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.