Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/SLSS-8HTML5
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Wagner Meira Junior | pt_BR |
dc.contributor.referee1 | Adriano Alonso Veloso | pt_BR |
dc.contributor.referee2 | Sebastián Alberto Urrutia | pt_BR |
dc.contributor.referee3 | Alexandre Plastino de Carvalho | pt_BR |
dc.creator | Carlos Henrique de Carvalho Teixeira | pt_BR |
dc.date.accessioned | 2019-08-14T08:56:19Z | - |
dc.date.available | 2019-08-14T08:56:19Z | - |
dc.date.issued | 2011-05-13 | pt_BR |
dc.identifier.uri | http://hdl.handle.net/1843/SLSS-8HTML5 | - |
dc.description.abstract | A graph is a universal data structure, useful to represent several objects and concepts.In the recent decades, the interest in graphs has been driven by a large amount of dataavailable. Examples include XML repositories, social networks, biological networks,and chemical graphs. Therefore, it is necessary to manage, query and analyze suchlarge graph data efficiently.The central problem of this thesis is the computation of the similarity betweengraphs in an efficient and effective manner. The proposed approach may be dividedinto two parts: (1) a transformation function, and (2) a signature function. A transformationfunction decomposes the input graph into approximate paths, which aresubstructures presented by this work. Approximate paths differ from simple paths byallowing gaps between nodes. Such flexible substructures are able to describe directand indirect relationships in graphs. The similarity between two graphs is computedthrough a kernel function based on the number of substructures shared by them. Sincethe number of substructures that represent a graph may be large, a signature functionapplies a hashing technique in order to provide a short descriptor for a set of substructures.The signatures are short enough to fit into the main memory and may estimatethe similarity between the sets efficiently, with theoretically guaranteed effectiveness.We have evaluated the proposed method using several real and synthetic datasets,from different application scenarios, such as information retrieval and classification.The results show that approximate paths may be used efficiently and achieve gainsw.r.t. the techniques from the literature. | pt_BR |
dc.description.resumo | Grafos são estruturas de dados universais capazes de representar objetos e conceitos. Nas últimas décadas, o interesse por essa estrutura tem sido impulsionado pela grande quantidade de dados modelados naturalmente como grafos. O objetivo deste trabalho é comparar dois grafos quaisquer de forma eficiente e eficaz, facilitando as análises de grandes bases de dados. Primeiro, os grafos são decompostos em subestruturas chamadas de caminhos aproximados. A similaridade entre dois grafos é, então, calculada em função do número de subestruturas compartilhadas entre eles. Visto que o conjunto de subestruturas gerado para representar um grafo pode ser grande, nós utilizamos técnicas de hashing para reduzí-lo a um conteúdo fixo e pequeno de informacão. Além de tornar possível a análise em memória principal, as assinaturas estimam a similaridade entre os conjuntos de forma eficiente, com qualidade assegurada. Os experimentos realizados em cenários reais mostram a efetividade do método proposto. | pt_BR |
dc.language | Português | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Ciência da Computação | pt_BR |
dc.subject.other | Teoria dos grafos | pt_BR |
dc.subject.other | Computação | pt_BR |
dc.subject.other | Mineração de dados (Computação) | pt_BR |
dc.title | Similaridade de grafos via hashing | pt_BR |
dc.type | Dissertação de Mestrado | pt_BR |
Appears in Collections: | Dissertações de Mestrado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
carloshenriquedecarvalhoteixeira.pdf | 4.7 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.