El Descubrimiento de Subgrupos (SD) es una técnica de minería de datos supervisada para identificar un conjunto de relaciones (subgrupos) entre atributos de un conjunto de datos con respecto a un atributo objetivo. Dos componentes clave de esta técnica son (i) la métrica utilizada para cuantificar un subgrupo extraído, llamada medida de calidad, y (ii) la estrategia de búsqueda utilizada, que determina cómo se explora el espacio de búsqueda y cómo se obtienen los subgrupos. La propuesta realizada en este trabajo consta de dos partes, (1) un nuevo y eficiente algoritmo de SD que se basa en la estrategia de exploración de clases de equivalencia y que utiliza una poda basada en estimación optimista, y (2) una estructura de datos utilizada al implementar el algoritmo para calcular refinamientos de subgrupos de manera fácil y eficiente. Una de las ventajas más importantes de este algoritmo es su fácil paralelización. Hemos probado el rendimiento de nuestro algoritmo de SD con respecto a otros algoritmos de SD de vanguardia bien conocidos en términos de tiempo de ejecución, uso máximo de memoria, subgrupos seleccionados y nodos visitados. Esto se completó utilizando una colección de conjuntos de datos estándar, bien conocidos y populares obtenidos de la literatura relevante. Los resultados confirmaron que nuestro algoritmo es más eficiente que los otros algoritmos considerados.