Virtualization is a key technology underlying cloud computing platforms, where applications encapsulated within virtual machines are dynamically mapped onto a pool of physical servers. In this paper, we argue that cloud providers can significantly lower operational costs, and improve hosted application performance, by accounting for affinities and conflicts between co-placed virtual machines. We show how these affinities can be inferred using location-independent VM characterizations called virtual footprints, and then show how these virtual footprints can be used to reshape the physical footprint of a VM---its physical resource consumption---to achieve higher VM consolidation and application performance in a cloud environment. We also identify three general principles for minimizing a virtual machine’”Ēs physical footprint, and discuss challenges in applying these principles in practice.