Data structure for optimal deduplication of common subsets
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).