1. A system for provisioning a new virtual machine instance on a target host based on an image of the new virtual machine instance, the system comprising: a local storage for storing images of virtual machine instances currently running on the target host; a virtual machine creator coupled to the local storage and running on the target host for constructing the image of the new virtual machine instance at least in part using the images of virtual machine instances currently running on the target host, wherein the image of the new virtual machine instance comprises one or more clusters; a similarity matrix coupled to the virtual machine creator and stored on the target host for identifying one or more clusters required to produce an image of each of the virtual machine instances currently running on the target host, wherein the similarity matrix comprises: a plurality of rows, each of the plurality of rows corresponding to a given cluster of the one or more clusters; a plurality of columns, each of the plurality of columns corresponding to an image of a given virtual machine instance running on the target host; and at each intersection of one of the plurality of rows and one of the plurality of columns, an indicator indicating whether the given cluster occurs in the given image; and a provisioning manager configured to: transmit a first request to the virtual machine creator, the request including an inquiry into an availability of free slots on the target host, the slots comprising a number of cores and a number of memories to be allocated to the new virtual machine instance; receive a first response from the virtual machine creator, the response including an indication of the availability of free slots; responsive to a determination the target host associated with the virtual machine creator has at least one available free slot, transmit a second request to the virtual machine creator, the second request including an inquiry into a percentage of the image of the new virtual machine instance available in the local storage of the target host; receive a second response from the virtual machine creator, the second response including a determination of the percentage of the image of the new virtual machine instance available in local storage on the local host, wherein the determination is made by a consultation to the similarity matrix; and provision, responsive to a determination the target host has a highest percentage of the image available in local storage in comparison to a plurality of additional target hosts, the new virtual machine instance on the target host.