In some examples, a system computes respective values for corresponding data value indicators added to and removed from a deduplication data store in which duplicated data values have been eliminated, where each respective data value indicator of the data value indicators represents presence of a unique data value in the deduplication data store. The system updates an estimator based on the respective values, to reflect an addition of a first data value indicator to the deduplication data store and a removal of a second data value indicator from the deduplication data store. The system computes, using the updated estimator, a parameter relating to data deduplication at the deduplication data store.