Repositório Digital

A- A A+

PathSim : um algoritmo para calcular a similaridade entre caminhos XML

.

PathSim : um algoritmo para calcular a similaridade entre caminhos XML

Mostrar registro completo

Estatísticas

Título PathSim : um algoritmo para calcular a similaridade entre caminhos XML
Outro título PathSim: A XML path similarity algorithm
Autor Vinson, Alexander Richard
Orientador Heuser, Carlos Alberto
Data 2007
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto Armazenamento : Dados
Consulta : Similaridade
XML (Linguagem de marcação)
[en] Comparison
[en] Paths
[en] Similarity
[en] XML
Resumo Algoritmos de similaridade que comparam dados expressos em XML são importantes em diversas aplicações que manipulam informações armazenadas nesse padrão. Sistemas de integração de dados XML e de consulta a instâncias XML são exemplos dessas aplicações. A utilização de funções de similaridade para efetuar as comparações nessas aplicações melhora seus resultados finais. A melhora ocorre porque as funções de similaridade possibilitam encontrar estruturas não idênticas às apresentadas nos parâmetros das consultas mas que armazenam informações relevantes. Uma característica importante que pode ser utilizada para definir se dois elementos XML representam o mesmo objeto real é os caminhos que chegam a estes elementos nas suas respectivas árvores. No entanto, os nodos que representam um determinado objeto real em duas instâncias XML diferentes podem se acessados por caminhos distintos, devido a opções de modelagem dos documentos. Portanto um algoritmo para calcular a similaridade entre caminhos XML é importante para as aplicações descritas acima. Neste contexto, esta dissertação objetiva desenvolver um algoritmo de similaridade entre caminhos XML. O resultado principal do trabalho é um algoritmo de similaridade entre caminhos XML, nomeado PathSim, que efetua o cálculo de similaridade entre dois caminhos baseado no número mínimo de operações de edição (inserção, remoção e substituição de nomes de elementos) necessárias para transformar um caminho no outro. Além deste algoritmo, foram desenvolvidas três funções de pré-processamento para simplificar os caminhos XML e melhoram os resultados do algoritmo. Adicionalmente, duas variações do algoritmo PathSim são apresentadas, uma incrementada com comparações entre combinações de nomes de elementos, nomeada PathSimC, e a outra auxiliada por técnicas de alinhamento, nomeada PathSimA. Experimentos utilizando documentos XML criados por terceiros, validam empiricamente os algoritmos PathSim e PathSimC.Nos experimentos, os algoritmos foram comparados a uma abordagem para mensurar a similaridade entre caminhos encontrada na literatura. Os algoritmos apresentam melhores resultados que o baseline. Os ganhos variam de acordo com o ambiente onde os caminhos foram extraídos e com as funções de pré-processamento que foram aplicadas aos caminhos.
Abstract Similarity algorithms for comparing XML data are important in various applications that manipulate information stored according to this standard. XML data integration systems and XML instance querying systems are examples of such applications. The use of similarity functions to evaluate comparisons in these applications improves their final results. The improvement occurs because similarity functions allow finding structures that are not identical to the query parameter but store relevant information. One important feature that may be used to define if two XML elements represent the same real world object is the paths that lead to those objects in their corresponding trees. However, the nodes that represent a specific real world object in two different XML instances may be accessed by distinct paths, due to XML design decisions. Thus a method for assessing the similarity of XML paths is important in the applications described above. In this context, the goal of this dissertation is to develop a XML path similarity algorithm. The main contribution of this work is a XML path similarity algorithm, named Path- Sim, that calculates the similarity between two paths by computing the minimum number of edit operations (element name insertions, deletions and substitutions) required to transform one path into another. Besides the algorithm, three preprocessing functions were developed to simplify XML paths and improve the results of the algorithm. Additionally, two variations of PathSim algorithm are presented, one enhanced with comparisons among combinations of element names, named PathSimC, and the other one assisted by alignment techniques, named PathSimA. Experiments using XML documents created by third parties validate the algorithms PathSim and PathSimC empirically. On the experiments, the algorithms are compared to a path similarity algorithm found in the literature. The proposed algorithms presents better results than the baseline. The gains vary according to the environment from which the paths were extracted and to the preprocessing functions applied.
Tipo Dissertação
URI http://hdl.handle.net/10183/10781
Arquivos Descrição Formato
000601058.pdf (567.3Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.