1. A method of providing a scalable representation of metadata for deduplicated storage systems, the method comprising: identifying shared data segments that are contained in a plurality of data objects in a deduplicated storage system; generating a data object centric graph, the generating comprising: creating vertices that represent the data objects; creating edges between the data objects, wherein an edge connecting two data objects indicates that the two data objects contain at least one shared data segment in common and each shared data segment between any two of the data objects is represented by at most one of the edges; and assigning an edge weight to the edges, each edge weight indicating a number of shared data segments in common between data objects connected by the edge; manipulating at least one of the data objects based on the data object centric graph, the manipulating including estimating at least one of a size of the data objects based on the data object centric graph and an upward bound of the size of the data objects based on the data object centric graph; receiving an update to a data object; and incrementally updating the data object centric graph to reflect the update.