We deal with the so-called missing data problem, which is the problem of imputing missing values in information systems. We propose a new algorithm, called ARSI algorithm, to address the imputation problem of missing values on categorical databases using the framework of Rough Set Theory. This algorithm can be seen as a refinement of ROUSTIDA algorithm and combines the approach of a generalized nonsymmetric similarity relation with a generalized discernibility matrix to predict the missing values on incomplete information systems. Computational experiments show that the proposed algorithm is as efficient and competitive as other imputation algorithms.