SAP: Similarity-aware partitioning for efficient cloud storage

Bharath Balasubramanian, Tian Lan, Mung Chiang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

13 Scopus citations


Given a set of files that show a certain degree of similarity, we consider a novel problem of deduplicating them (eliminating redundant chunks) across a set of distributed servers in a manner that is: (i) space-efficient: the total space needed to deduplicate and store the files is minimized and, (ii) access-efficient: each file can be accessed by communicating with a bounded number of servers, thereby minimizing networkaccess times in congested data center networks. A spaceoptimal solution in which we first deduplicate all the files and then distribute them across the servers (referred to as chunk-distribution), may require communication with many servers to access each file. On the other hand, an access-efficient solution in which we randomly partition the files cross the servers, and then store their unique chunks on each server may not exploit the similarities across files to reduce the space overhead. In this paper, we first show that finding an access-efficient, space optimal solution is an NP-Hard problem. Following this, we present the similarity-aware-partitioning (SAP) algorithms that find access-efficient solutions within polynomial time complexity and guarantees bounded space overhead for arbitrary files. Our experimental verification on files from Dropbox and CNN confirm that the SAP technique is much more space-efficient than random partitioning, while maintaining compression ratio close to the chunk-distribution solution.

Original languageEnglish (US)
Title of host publicationIEEE INFOCOM 2014 - IEEE Conference on Computer Communications
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages9
ISBN (Print)9781479933600
StatePublished - 2014
Event33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014 - Toronto, ON, Canada
Duration: Apr 27 2014May 2 2014

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Other33rd IEEE Conference on Computer Communications, IEEE INFOCOM 2014
CityToronto, ON

All Science Journal Classification (ASJC) codes

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'SAP: Similarity-aware partitioning for efficient cloud storage'. Together they form a unique fingerprint.

Cite this