| Revista: | Computación y sistemas |
| Base de datos: | PERIÓDICA |
| Número de sistema: | 000352727 |
| ISSN: | 1405-5546 |
| Autores: | Gago Alonso, Andrés1 Carrasco Ochoa, Jesús A2 Medina Pagola, José E1 Martínez-Trinidad, José2 |
| Instituciones: | 1Centro de Aplicaciones de Tecnologías de Avanzada, Departamento de Minería de Datos, La Habana. Cuba 2Instituto Nacional de Astrofísica, Optica y Electrónica, Departamento de Ciencias de la Computación, Tonantzintla, Puebla. México |
| Año: | 2011 |
| Periodo: | Oct-Dic |
| Volumen: | 15 |
| Número: | 2 |
| Paginación: | 251-265 |
| País: | México |
| Idioma: | Inglés |
| Tipo de documento: | Artículo |
| Enfoque: | Aplicado, descriptivo |
| Resumen en español | La minería de subgrafos conexos frecuentes es un problema interesante con amplias aplicaciones en la vida práctica. La mayor parte de los algoritmos para este tipo de minería detectan los candidatos duplicados utilizando pruebas de forma canónica. Este tipo de pruebas tienen una alta complejidad computacional, lo cual afecta el desempeño de los algoritmos de minería de grafos. En este artículo se proponen nuevas propiedades para reducir el número de pruebas de forma canónica en este tipo de minería. Basado en estas propiedades, se propone un nuevo algoritmo llamado gRed. Los resultados experimentales en colecciones de datos reales muestran el impacto de las nuevas propiedades en la eficiencia de gRed, reduciendo el número de pruebas de forma canónicas con respecto a gSpan. Además, el desempeño de gRed es comparado respecto gSpan y otros algoritmos reportados en el estado del arte |
| Resumen en inglés | Frequent connected subgraph (FCS) mining is an interesting problem with wide applications in real life. Most of the FCS mining algorithms have been focused on detecting duplicate candidates using canonical form tests. Canonical form tests have high computational complexity, and therefore, they affect the efficiency of graph miners. In this paper, we introduce novel properties to reduce the number of canonical form tests in FCS mining. Based on these properties, a new algorithm for FCS mining called gRed is presented. The experimentation on real world datasets shows the impact of the proposed properties on the efficiency of gRed reducing the number of canonical form tests regarding gSpan. Besides, the performance of our algorithm is compared against gSpan and other state–of–the–art algorithms |
| Disciplinas: | Ciencias de la computación |
| Palabras clave: | Procesamiento de datos, Tecnología de la información, Minería de datos, Algoritmos |
| Keyword: | Computer science, Data processing, Information technology, Data mining, Algorithms |
| Texto completo: | Texto completo (Ver HTML) |
