A multimedia database is queried using an iterative step in which, at the current iteration, a portion retrieved from the database is determined using an ordered set of query criteria worked out at the previous iteration or at a previous initialization step if the current iteration is the first iteration, and using a criteria vector comprising characteristic values of a predetermined set of query criteria for the portion retrieved from the database. The criteria vector is initialized at the initialization step if the current iteration is the first iteration, and determined during the previous iteration otherwise.