Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/51806
Type: | Tese |
Title: | Graph pattern mining: consolidating models, systems, and abstractions |
Authors: | Vinícius Vitor dos Santos Dias |
First Advisor: | Dorgival Olavo Guedes Neto |
First Referee: | Srinivasan Parthasarathy |
Second Referee: | Arlei Lopes da Silva |
Third Referee: | Ítalo Fernando Scotá Cunha |
metadata.dc.contributor.referee4: | Vinícius Fernandes dos Santos |
metadata.dc.contributor.referee5: | Wagner Meira Júnior |
Abstract: | Mineração de padrões em grafos (MPG) se refere a uma classe de problemas envolvendo o processamento de subgrafos extraídos de um único grafo maior. Aplicações para algoritmos de MPG incluem consultas por subgrafos com certas propriedades de interesse, identificação de estruturas em redes biológicas, caracterização de redes sociais, entre outras. Desenvolver algoritmos de MPG é desafiador principalmente pela inerente presença de sub-rotinas não-triviais lidando com conceitos complexos em teoria de grafos, como identificação de isomorfismos. Neste contexto, sistemas de propósito geral para MPG surgem como uma alternativa para melhorar a experiência de usuários com esses algoritmos. Entretanto, sistemas de propósito geral para MPG falham em prover um modelo que seja de fácil entendimento e, ao mesmo tempo, qualificado para exprimir algoritmos alternativos para um mesmo problema usando diferentes paradigmas de enumeração de subgrafos, limitando a integração com fluxos de análise de dados atuais. Além disso, como sistemas de MPG são tão heterogêneos no que se refere aos paradigmas suportados e ambientes de execução, análises experimentais existentes são incapazes de diferenciar se as diferenças encontradas no desempenho dos sistemas são melhor explicadas pelos algoritmos utilizados ou pelos detalhes de implementação. Nesta tese, propomos um modelo para MPG baseado em primitivas, uma implementação distribuída escalável como prova de conceito para o modelo e uma avaliação experimental extensiva dos paradigmas mais usados por sistemas de MPG. Nós demonstramos empiricamente a efetividade de nossas soluções ao observar um desempenho competitivo em relação às propostas existentes sem sacrificar a expressividade dos algoritmos ou a capacidade de composição dos operadores. Nossos resultados mostram ainda que nenhum paradigma é melhor em todo cenário de aplicação e acreditamos que essa e outras de nossas descobertas podem guiar interessados em direção a sistemas de MPG mais otimizados no futuro. |
Abstract: | Graph Pattern Mining (GPM) refers to a class of problems involving the processing of subgraphs extracted from larger graphs. Applications to GPM algorithms include querying subgraphs with given properties of interest, identifying motif structures in biological networks, characterizing social media, among others. GPM algorithms are challenging to develop due to inherently subroutines that include non-trivial graph theory concepts and methods such as isomorphism. General-purpose GPM systems emerge as a solution to improve the user experience with such algorithms. However, general-purpose GPM systems fail in providing a consistent model that is simple to understand and qualified to express alternative algorithms for the same problem via different paradigms for subgraph enumeration, limiting the integration with modern data analytics pipelines. Furthermore, because GPM systems are so heterogeneous in terms of supported paradigms and computing architecture, existing experimental evaluations are unable to distinguish whether performance differences are best explained by algorithmic strategies or implementation details. In this work we propose a primitive-based model for GPM, a proof of concept distributed implementation of that model, and an extensive experimentation analysis of popular algorithmic paradigms used in GPM systems. We demonstrate empirically the effectiveness of our model by showing competitive performance against state-of-the-art systems without sacrificing the expressiveness of algorithms or the composability of operators. Our experimental results also show that no single paradigm is best for every application scenario, and we believe that our findings may guide practitioner towards more optimized GPM systems in the future. |
Subject: | Computação – Teses Mineração de padrões em grafos – Teses Sistemas distribuídos – Teses |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Ciência da Computação |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/51806 |
Issue Date: | 24-Mar-2023 |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
tese-vinicius-dias-2023.pdf | tese com a correção de não incluir número de páginas antes da introd. | 4.1 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.