Abstract: Computing reduction of attributes plays an essential role in the framework of supervised learning based on rough sets. Attribute reduction algorithm based on discernibility matrix is one of the commonly used attribute reduction algorithms. Given an information system, all reductions can be found by using this algorithm. However, this algorithm suffers from the main problems: large memory requirement and large response time needed. Especially, for a large database, it is the bottleneck to store the discernibility matrix. To tackle this problem effectively, an attribute reduction algorithm based on instance selection is proposed. The algorithm consists of three stages: firstly, the most informative instances are selected from the training set; secondly, the discernibility matrix is computed by using the selected instances; finally, all reductions can be found. The experimental results show that the proposed method can efficiently reduce the computational complexity both of time and space especially on large databases.