Duplicates of immutable data objects are identified and deduplicated. This is performed by performing a bottom up deduplication, such that objects in hierarchically lower levels of a data structure are deduplicated first. Deduplication identifies duplicates of a particular object through value equality analysis and replaces pointers to duplicate objects and the duplicate objects themselves, with a reference to the particular object. This process is repeated for hierarchically higher data objects, but where the value equality analysis includes, among other things, evaluating the equality of references to hierarchically lower data objects.