De-duplication algorithms have been used extensively in the backup and recovery realm to exploit the temporal data redundancy on the versioning nature of backup applications. More recently de-duplication algorithms have progressed into the primary storage area where more spatial data exist, in either case increasing the efficiency of the usable storage capacity. In parallel another industry trend is the use of cloud resources to provide a utility model for software and infrastructure services. Cloud resources aid in decreasing the provisioning time for applications and infrastructure, while increasing the scalability to meet the elastic nature of application and infrastructure requirements. Using the de-duplication algorithms within cloud resources is the next logic step to increase the efficiency and cost related to cloud computing.
Cloud environments involve pricing models for both computing and storage. In this work, we examine the tradeoffs between computing costs and reduction in storage costs (due to higher de-duplication) for a number of popular de-duplication algorithms. Since the main factor impacting the computing cost is the memory availability in different type of instances, we also develop a methodology for predicting the memory requirements for executing a given algorithm on a particular dataset.