A system and method for enriching a concept database. The method includes determining, based on at least one signature of a first multimedia data element (MMDE) and signatures of a plurality of existing concepts in the concept database, at least one first concept among the plurality of existing concepts, wherein each of the at least one first concept matches a portion of the at least one signature of the first MMDE; generating a reduced representation of the first MMDE, wherein generating the reduced representation further comprises removing the portion of the first MMDE matching the at least one first concept; comparing the reduced representation of the first MMDE to signatures representing a plurality of second MMDEs to determine a plurality of matching second MMDEs; generating, based on the reduced representation of the first MMDE and the plurality of matching second MMDEs, at least one second concept; and adding the generated at least one second concept to the concept database.