A method and system for generating a large-scale database of heterogeneous speech are provided. The method includes transcribing a plurality of multimedia signals retrieved from a large text database and a speech database; randomly selecting a plurality of speech segments from the plurality of multimedia signals, wherein each speech segment of the plurality of speech segments is of a random length; generating a plurality of signatures based on the plurality of speech segments; and populating the large-scale database with the plurality of signatures respective of the plurality of multimedia signals.