A system for generating signatures of an input multimedia data element comprises a partitioning unit for recursively partitioning the input multimedia data element into a plurality of multimedia data elements, wherein each of the plurality of the minimum size multimedia data elements is a minimal partition of the input multimedia data elements; a signature generator for generating for each of the plurality of minimum size multimedia data elements a respective signature; and a storage unit for storing the respective signatures respective of the plurality of minimum size multimedia data elements.