1. A computing device for performing concatenative speech synthesis by a processing unit of the computing device, the computing device comprising: a memory; a processor coupled to the memory, the processor executing a text to speech (TTS) application in conjunction with instructions stored in the memory, wherein the TTS application is configured to: determine, based on a matrix of concatenation costs, feature vectors for speech segments, wherein some of the speech segments occur at asynchronous time intervals; apply distance weighting to one of: the speech segments and at least two consecutive speech segments, wherein the distance weighting is based on feature vectors associated with the speech segments or is based on feature vectors associated with the at least two consecutive speech segments; cluster the speech segments into a predefined number of groups such that an average distance between speech segments within each group is minimized; select a representative speech segment for each group; and generate a compressed concatenation cost matrix based on the representative speech segments.